The discussion 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 (i = (n/2); i > 0; i--)
heapifySubtree(data, i-1, n);

For example, with n = 10, we will end up making the following sequence of activations:
heapifySubtree(data, 4, 10);
heapifySubtree(data, 3, 10);
heapifySubtree(data, 2, 10);
heapifySubtree(data, 1, 10);
heapifySubtree(data, 0, 10);

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

For this project, reimplement makeHeap, as outlined above.

Transcribed Image Text:

private static void heapifySubtree( int[ ] data, int root0fSubtree, int n // Precondition: data is an array with at least // n elements, and rootOfSubtree < n. We will // consider data to represent a complete // binary tree, and in this representation the // node at data[rootOfSubtree] is the root of // a subtree called s. This subtree s is already // a heap, except that its root might be out of // place. // Postcondition: The subtree s has been // rearranged so that it is now a valid heap.