1. The discussion on page 656 shows our algorithm for building the initial heap in the heapsort algorithm. The algorithm is reasonably efficient, but we can make it even more efficient. The more...

1. The discussion on page 656 shows our algorithm for building the initial heap in the heapsort algorithm. The algorithm is reasonably efficient, but we can make it even more efficient. The more efficient algorithm uses a method that creates a heap from a subtree of the complete binary tree. This method has the following specification:

You can write the heapifySubtree method yourself. Using this method, you can make an entire
n-element array into a heap with the algorithm:

For example, with
n
= 10, we will end up making the following sequence of activations:

It turns out that this method is actually
O(n) rather than
O(n
log
n).

For this project, reimplement makeHeap, as outlined above.