8.4.6 Reheaping

Think of step 1 of the heap sorting algorithm as phase I, in which a heap is created. The execution of step 2 until the records are sorted is phase II. In phase II, the root element of the heap is removed and output. The program must then reheap. This may be done in two ways.

One is to allow the "gap" created at the root by removal of its record to shift down by comparing its two successors and interchanging the larger of the two successors with the gap, then repeating this process until the gap is at a terminal node. A convenient way to do this is to replace the record removed from the root by a "negative infinity" and invoke the shift down function referred to earlier for the second algorithm.

A second way to reheap is to replace the gap with the rightmost record at greatest depth. (Actually, any record with no successors will do.) The same shift function may be invoked to reheap.

Since the length of the longest path in a complete binary tree is O(lg n), the reheaping after each record is removed can take time at most O(lg n). Because n records will ultimately be removed, the total time required for phase II will be at most O(n lg n). For either implementation of phase I, the total heapsort time is O(n lg n). This was achieved by "spreading out" the records along paths of a complete binary tree, and, in effect, doing insertions only along the path from a record to the root.

We have been dealing with a max heap, in which the largest record is at the top. A min heap, with the smallest record at the top, is dealt with similarly. The only difference is that interchanging occurs when a successor's key is smaller, rather than larger.