6.4 The heapsort algorithm
The heapsort algorithm starts by using BUILD-MAX-HEAP to build a max-heap on the input array A[1 ‥ n], where n = length[A]. Since the maximum element of the array is stored at the root A[1], it can be put into its correct final position by exchanging it with A[n]. If we now "discard" node n from the heap (by decrementing heap-size[A]), we observe that A[1 ‥ (n - 1)] can easily be made into a max-heap. The children of the root remain max-heaps, but the new root element may violate the max-heap property. All that is needed to restore the max-heap property, however, is one call to MAX-HEAPIFY(A, 1), which leaves a max-heap in A[1 ‥ (n - 1)]. The heapsort algorithm then repeats this process for the max-heap of size n - 1 down to a heap of size 2. (See Exercise 6.4-2 for a precise loop invariant.)
Figure 6.4 shows an example of the operation of heapsort after the max-heap is initially built. Each max-heap is shown at the beginning of an iteration of the for loop of lines 2-5.
The HEAPSORT procedure takes time O(n lg n), since the call to BUILD-MAX-HEAP takes time O(n) and each of the n - 1 calls to MAX-HEAPIFY takes time O(lg n).
Exercises 6.4-1
Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the array A = 〈5, 13, 2, 25, 7, 17, 20, 8, 4〉.
Exercises 6.4-2
Argue the correctness of HEAPSORT using the following loop invariant:
-
At the start of each iteration of the for loop of lines 2-5, the subarray A[1 ‥ i] is a max-heap containing the i smallest elements of A[1 ‥ n], and the subarray A[i + 1 ‥ n] contains the n - i largest elements of A[1 ‥ n], sorted.
Exercises 6.4-3
What is the running time of heapsort on an array A of length n that is already sorted in increasing order? What about decreasing order?
Exercises 6.4-4
Show that the worst-case running time of heapsort is Ω(n lg n).
Exercises 6.4-5: ★
Show that when all elements are distinct, the best-case running time of heapsort is Ω(n lg n).