Determine the best-, worst-, and average-case time complexities of each

public method of the MaxHeap class by using a recursion tree.

Show work.

What is the total space complexity of each public method of the MaxHeap

class? For recursive functions, specify both the implicit and explicit space complexities.

This is C++

1 Max Binary Heaps #include #include #include heap: public: int size() const { return heap.size(); int maxLookup() const { return heap [0]; void extractMax() { remove(0); void insert(int data) { // Add data to the end of the heap heap.push_back(data); // Bubble up the element to its correct position int index - heap.size() - 1; bubbleUp (index); void remove(int index) { // Swap with the last element in the heap swap(heap[index], heap Cheap.size() - 1]); // Remove the element heap.pop_back: // Bubble down the element that was just moved into index bubbleDown(index); private: static int parent(int index) { return (index - 1) / 2; static int left Child(int index) { return 2. index + 1; static int right Child(int index) { return 2. index + 2: bool hasLeftChild(int index) const { return left Child(index) heap (parent (index)]) { // ... swap it with its parent swap(heap [index], heap[parent (index)]); // and set index to follow the element up through the tree index-parent (index); void bubbleDown(int index) { // Find the index of the largest element among [index, left Child, right Child int largest index; if (hasLeft Child(index) kk heap[leftChild(index)] > heap [largest]) { largest - leftChild(index); 11 ChasRightChild(index) kk heap [rightChild(index)] > heap[largest]) { largest - rightChild (index): // If the largest is indes, then we're done, otherwise... if (largest index) { // ... swap the data at indes with the data at largest swapCheap Cindex), heap[largest]); // and continue bubbling down from where you just moved the element. bubbleDown (largest); // Or here's an iterative example // int largest index // while (true) { // if (hasLeft Child (index) Theap leftChild(index)]> heap largest)) { largest - leftChild(index); // if (hasRightChild (inden) heap [rightChild(index)] > heap largest]) { largest - rightChild (inder); // If the largest is index, then we're done, otherwise... if (largest -- index) { // Nothing to swap, bubble down is complete break; // // ... swap the data at index with the data at largest swap (heap/index), heap [largest]); index = largest; // int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT/ Max Heap heap: int commandCount; cin >> commandCount; for (int i = 0; i > command; if (command == "size") { cout > data; heap.insert (data); } else if (command "delete") { int index; cin >> index; heap.remove(index); } else { throw runtime_error("Invalid command"); return 0