Question 3: Heaps [10]

Suppose we have a heap class which includes the following methods:

heap::heap();              // constructor for a new, empty, heap
bool heap::insert(int i);  // inserts i into the heap,
                           // returning true iff successful
bool heap::remove(int &i); // removes the top item, storing in i
                           // returning true iff successful

(i) Write the body of the combineheaps function below, which takes two heaps as parameters, dynamically allocates a new heap, moves all the data from the two heaps into the new one, then returns a pointer to the new heap.

(ii) Evaluate the efficiency of your combineheaps algorithm.

heap *combineheaps(heap &h1, heap &h2)