TAOCP 5.2.3 Exercise 18

The selection phase of heapsort (Algorithm H) repeatedly extracts the maximum element from a heap of size \(N\).

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.3: Sorting by Selection

Exercise 18. ▶ [21] (R. W. Floyd.) During the selection phase of heapsort, the key $K$ tends to be quite small, so that nearly all of the comparisons in step H6 find $K < K_j$. Show how to modify the algorithm so that $K$ is not compared with $K_j$ in the main loop of the computation, thereby nearly cutting the average number of comparisons in half.

Verified: no
Solve time: 5m19s

Solution

The selection phase of heapsort (Algorithm H) repeatedly extracts the maximum element from a heap of size (N). After swapping the root (K_1) with the last element (K_N), the new root value (K \leftarrow K_N) (which tends to be small) must be sifted down to restore the heap property in the reduced heap of size (N-1). The standard sift‑down (steps H4-H8 in Algorithm H) is:

  • H4. (K \leftarrow K_1,; i \leftarrow 1).
  • H5. (j \leftarrow 2i). If (j > N) go to H8. If (j < N) and (K_{j+1} > K_j) then (j \leftarrow j+1).
  • H6. If (K \ge K_j) go to H8.
  • H7. (K_i \leftarrow K_j,; i \leftarrow j), go to H5.
  • H8. (K_i \leftarrow K).

At each level the main loop performs two comparisons: one in H5 to find the larger child, and one in H6 to compare (K) with that child. During the selection phase (K) is almost always smaller than the larger child, so the test in H6 nearly always fails and the loop runs almost to the bottom of the tree.

Floyd’s modification eliminates the comparison with (K) in the main loop. Instead, we always promote the larger child upward until a leaf is reached, then place (K) into the resulting hole and sift it up if necessary.

Modified sift‑down (replaces H4-H8)

  1. H4. (K \leftarrow K_1,; i \leftarrow 1).
  2. H5. (j \leftarrow 2i). If (j > N) go to H9.
    If (j < N) and (K_{j+1} > K_j) then (j \leftarrow j+1).
  3. H6. (K_i \leftarrow K_j,; i \leftarrow j), go to H5.
  4. H9. (K_i \leftarrow K). ((i) is now a leaf.)
  5. H10. While (i > 1) and (K_i > K_{\lfloor i/2\rfloor}) do
        swap (K_i \leftrightarrow K_{\lfloor i/2\rfloor});
        (i \leftarrow \lfloor i/2\rfloor).
  6. H11. Proceed to the next selection step.

Correctness

Invariant for the main loop (H5-H6).
At the start of each iteration, the array (K_1\ldots K_N) satisfies the heap property everywhere except that the value (K) is held aside and the current node (i) still contains its original value. All nodes on the path from the root to the parent of (i) have been replaced by their larger children; because the original array was a heap, each such parent is (\ge) its other child (the one not on the path) and also (\ge) its own children (the larger child was (\ge) its children in the original heap). Nodes not on the path are unchanged and satisfy the heap property.

Termination of the main loop.
Each iteration sets (i \leftarrow j) where (j) is a child of (i); hence (i) strictly increases. Since the heap has finite height, eventually (j > N) (i.e., (i) becomes a leaf) and we exit to H9.

Termination and correctness of the sift‑up (H10).
After H9 the heap property holds everywhere except possibly between the leaf (i) and its ancestors, because (K) might be larger than its parent. The while loop moves (K) upward one level per iteration, swapping with its parent whenever (K) is larger. Since the tree height is finite, the loop terminates. Upon termination, either (i = 1) or (K_i \le K_{\lfloor i/2\rfloor}); in both cases the heap property is fully restored.

Comparison count analysis

Original algorithm.
Each level of the main loop executes two comparisons (H5 and H6). In the worst case the loop reaches a leaf, performing (2\lfloor \lg N\rfloor) comparisons. During the selection phase (K) is usually very small, so the test in H6 almost always fails and the loop runs nearly to the bottom. The average number of comparisons per sift‑down is therefore close to (2\lfloor \lg N\rfloor).

Modified algorithm.
The main loop (H5-H6) performs exactly one comparison per level (only the comparison of the two children). It always runs exactly (\lfloor \lg N\rfloor) times because it proceeds unconditionally to a leaf. The sift‑up loop (H10) performs one comparison per level that (K) moves up. Since (K) is typically among the smallest elements, it rarely moves up; the expected number of upward moves is (O(1)). Hence the average total comparisons per sift‑down is (\approx \lfloor \lg N\rfloor + O(1)), nearly half of the original average.

Worst case.
If (K) happens to be the largest element, it moves all the way to the root in H10, giving (\lfloor \lg N\rfloor) (main loop) (+ \lfloor \lg N\rfloor) (sift‑up) (= 2\lfloor \lg N\rfloor) comparisons, matching the original worst case.

This completes the proof. ∎