6.4 The heapsort algorithm

6.4-1

Using figure 6.4 as a model, illustrate the operation of $\text{HEAPSORT}$ on the array $A = \langle 5, 13, 2, 25, 7, 17, 20, 8, 4 \rangle$.

$$ \begin{aligned} \langle 5, 13, 2, 25, 7, 17, 20, 8, 4 \rangle \\ \langle 5, 13, 20, 25, 7, 17, 2, 8, 4 \rangle \\ \langle 5, 25, 20, 13, 7, 17, 2, 8, 4 \rangle \\ \langle 25, 5, 20, 13, 7, 17, 2, 8, 4 \rangle \\ \langle 25, 13, 20, 5, 7, 17, 2, 8, 4 \rangle \\ \langle 25, 13, 20, 8, 7, 17, 2, 5, 4 \rangle \\ \langle 4, 13, 20, 8, 7, 17, 2, 5, 25 \rangle \\ \langle 20, 13, 4, 8, 7, 17, 2, 5, 25 \rangle \\ \langle 20, 13, 17, 8, 7, 4, 2, 5, 25 \rangle \\ \langle 5, 13, 17, 8, 7, 4, 2, 20, 25 \rangle \\ \langle 17, 13, 5, 8, 7, 4, 2, 20, 25 \rangle \\ \langle 2, 13, 5, 8, 7, 4, 17, 20, 25 \rangle \\ \langle 13, 2, 5, 8, 7, 4, 17, 20, 25 \rangle \\ \langle 13, 8, 5, 2, 7, 4, 17, 20, 25 \rangle \\ \langle 4, 8, 5, 2, 7, 13, 17, 20, 25 \rangle \\ \langle 8, 4, 5, 2, 7, 13, 17, 20, 25 \rangle \\ \langle 8, 7, 5, 2, 4, 13, 17, 20, 25 \rangle \\ \langle 4, 7, 5, 2, 8, 13, 17, 20, 25 \rangle \\ \langle 7, 4, 5, 2, 8, 13, 17, 20, 25 \rangle \\ \langle 2, 4, 5, 7, 8, 13, 17, 20, 25 \rangle \\ \langle 5, 4, 2, 7, 8, 13, 17, 20, 25 \rangle \\ \langle 2, 4, 5, 7, 8, 13, 17, 20, 25 \rangle \\ \langle 4, 2, 5, 7, 8, 13, 17, 20, 25 \rangle \\ \langle 2, 4, 5, 7, 8, 13, 17, 20, 25 \rangle \end{aligned} $$

6.4-2

Argue the correctness of $\text{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.

Initialization: The subarray $A[i + 1..n]$ is empty, thus the invariant holds.

Maintenance: $A[1]$ is the largest element in $A[1..i]$ and it is smaller than the elements in $A[i + 1..n]$. When we put it in the $i$th position, then $A[i..n]$ contains the largest elements, sorted. Decreasing the heap size and calling $\text{MAX-HEAPIFY}$ turns $A[1..i - 1]$ into a max-heap. Decrementing $i$ sets up the invariant for the next iteration.

Termination: After the loop $i = 1$. This means that $A[2..n]$ is sorted and $A[1]$ is the smallest element in the array, which makes the array sorted.

6.4-3

What is the running time of $\text{HEAPSORT}$ on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?

Both of them are $\Theta(n\lg n)$.

If the array is sorted in increasing order, the algorithm will need to convert it to a heap that will take $O(n)$. Afterwards, however, there are $n - 1$ calls to $\text{MAX-HEAPIFY}$ and each one will perform the full $\lg k$ operations. Since:

$$\sum_{k = 1}^{n - 1}\lg k = \lg((n - 1)!) = \Theta(n\lg n).$$

Same goes for decreasing order. $\text{BUILD-MAX-HEAP}$ will be faster (by a constant factor), but the computation time will be dominated by the loop in $\text{HEAPSORT}$, which is $\Theta(n\lg n)$.

6.4-4

Show that the worst-case running time of $\text{HEAPSORT}$ is $\Omega(n\lg n)$.

This is essentially the first part of exercise 6.4-3. Whenever we have an array that is already sorted, we take linear time to convert it to a max-heap and then $n\lg n$ time to sort it.

6.4-5 $\star$

Show that when all elements are distinct, the best-case running time of $\text{HEAPSORT}$ is $\Omega(n\lg n)$.

This proved to be quite tricky. My initial solution was wrong. Also, heapsort appeared in 1964, but the lower bound was proved by Schaffer and Sedgewick in 1992. It's evil to put this an exercise.

Let's assume that the heap is a full binary tree with $n = 2^k - 1$. There are $2^{k - 1}$ leaves and $2^{k - 1} - 1$ inner nodes.

Let's look at sorting the first $2^{k - 1}$ elements of the heap. Let's consider their arrangement in the heap and color the leaves to be red and the inner nodes to be blue. The colored nodes are a subtree of the heap (otherwise there would be a contradiction). Since there are $2^{k - 1}$ colored nodes, at most $2^{k - 2}$ are red, which means that at least $2^{k - 2} - 1$ are blue.

While the red nodes can jump directly to the root, the blue nodes need to travel up before they get removed. Let's count the number of swaps to move the blue nodes to the root. The minimal case of swaps is when

there are $2^{k - 2} - 1$ blue nodes and
they are arranged in a binary tree.

If there are $d$ such blue nodes, then there would be $i = \lg d$ levels, each containing $2^i$ nodes with length $i$. Thus the number of swaps is,

$$\sum_{i = 0}^{\lg d}i2^i = 2 + (\lg d - 2)2^{\lg d} = \Omega(d\lg d).$$

And now for a lazy (but cute) trick. We've figured out a tight bound on sorting half of the heap. We have the following recurrence:

$$T(n) = T(n / 2) + \Omega(n\lg n).$$

Applying the master method, we get that $T(n) = \Omega(n\lg n)$.