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

Intuitively, HEAPSORT is required to perform a certain amount of structural work regardless of how optimal the input is. We have established in earlier exercises that BUILD-MAX-HEAP takes \(\Theta(n)\) time, but what about the value-extraction portion of HEAPSORT? I will show that this portion of the algorithm winds up dominating the runtime.

HEAPSORT will perform the following steps exactly \(n\) times:

1. Swap the root with the last element.

2. Shrink the heap size by one.

3. Call HEAPIFY on the root.

If we had a situation where keys can be equal, it would be possible that after swapping (step 1) the root is \(\ge\) both children in which case calling HEAPIFY on the root would do nothing. But the case we are considering does not allow for this because all keys are distinct. This introduces a new structural reality to the operation of HEAPSORT: after performing steps 1 and 2, the new root is never the maximum value among the remaining elements which means that HEAPSORT must perform at least one swap. In fact, since the element we swapped into root position was originally a leaf node, we know that we must continue swapping elements until it once again finds itself in a leaf position because in a max-heap with distinct keys all children are smaller than their parents, therefore the leaf node we just moved to the root position is smaller than every node on the path from the new root to a leaf position. This gives us a best-case cost of \(\Omega(\lg n)\) for each iteration of the primary for loop of HEAPSORT, which we know must occur exactly \(n\) times.

Thus the best-case running time of HEAPSORT on a heap with distinct elements is \(\Omega(n \lg n)\).