9.13* Case study: In-place heapsort

As already mentioned in [@heaps:simple-heapsort], we can use a heap to implement a very simple sorting algorithm:

1. Insert all elements from the unsorted array into a min-heap.
2. Remove each element in turn from the heap, putting it in its right place in the original array.

This simple algorithm has the same optimal time complexity as Mergesort. But it is not in-place, and it is in practice much slower than Mergesort.

In Section 9.12 we saw that there is a more efficient way of turning an array into a heap, by using the buildHeap operation. We can use this to implement a faster and in-place version of Heapsort.

The crucial step here is to use a max-heap, which might seem counter-intuitive. After building the heap we tweak the removeMax operation a little, so that it keeps the removed element, but puts it at the end of the array. This is why we need a max-heap – because the first element we remove will be put at the very end of the array. Here is an overview of the idea:

• First, turn the array into a max-heap, using buildHeap.
• Remove the maximum element, and put it at the end of the array. Then decrease the size of the heap – this will make the maximum element to be outside of the heap.
• Now remove the second largest element, and put it at the second final place. And decrease the size of the heap.
• Then remove the third largest element, and so on.
• Finally, when the heap is exhausted the internal array is sorted.

A complete implementation is as follows.

heapsort(arr):
    // First, convert the array to a max heap.
    heap = new MaxHeap()
    heap.buildHeap(arr)

    // Then, repeatedly remove each maximum element from the heap,
    // and put it just after the heap.
    n = heap.size
    for size in n-1, n-2 .. 0:
        heap.swap(0, size)  // Put the max element at the end of the heap.
        heap.size = size    // Change the heap size so it excludes the max element.
        heap.siftDown(0)    // Now, sift the temporary root down.

9.13.1 Analysis of in-place Heapsort

Here is an analysis of the time complexity of Heapsort:

• The first step in Heapsort is to heapify the array. This will cost O(n) running time for an array of size n.
• Then it swaps each element with the root node and “sifts” it down the heap.
  • Sifting down is logarithmic, O(\log(n)), in the worst case, since the height of the tree is logarithmic.
  • And this is done for each of the n elements in the array.
• So, the second loop is linearithmic, O(n \log(n)).

Therefore the worst-case complexity of Heapsort is linearithmic, O(n \log(n)).

While typically slower than Quicksort by a constant factor (because unloading the heap using removeMax is somewhat slower than Quicksort’s series of partitions), Heapsort has one special advantage over the other sorts studied so far. Building the heap is relatively cheap, requiring O(n) time. Removing the maximum-valued record from the heap requires O(\log(n)) time in the worst case. Thus, if we wish to find the k records with the largest key values in an array, we can do so in time O(n + k \log(n)). If k is small, this is a substantial improvement over the time required to find the k largest-valued records using one of the other sorting methods described earlier (many of which would require sorting all of the array first). One situation where we are able to take advantage of this concept is in the implementation of Kruskal’s algorithm for minimum spanning trees. That algorithm requires that edges be visited in increasing order (so, use a min-heap), but this process stops as soon as the MST is complete. Thus, only a relatively small fraction of the edges need be sorted.

Another special case arises when all of the records being sorted have the same key value. This represents the best case for Heapsort. This is because removing the smallest value requires only constant time, since the value swapped to the top is never pushed down the heap.