Understanding Heapsort

Heapsort follows a very simple idea:

• Push all items in the list on a heap
• Pop all items from the heap. The heap guarantees that the items are sorted, because it will always pop the minimum element in the heap

Subsequently, a heapsort implementation typically is trivial. The following code uses the MinHeap class developed in the heaps article:

def heapsort(A):
    h = MinHeap()

    # push-em-all
    for item in A:
        h.Insert(item)

    # pop-em-all
    for i in range(len(A)):
        A[i] = h.ExtractMin()

The same code, using the heapq module from the Python Standard Library:

def heapsort(A):
    h = []

    # push-em-all
    for value in A:
        heappush(h, value)

    # pop-em-all
    for i in range(len(A)):
        A[i] = heappop(h)

The real fun starts if you compare this to the quicksort implementations developed in the quicksort article. It turns out that heapsort is dramatically faster than quicksort, in Python. Probably because of a combination of simplicity of algorithm and lack of recursion (and Python doesn't perform particularily well on recursion).

At the end of mergesort we pointed out a situation where both quicksort implementations break badly: if asked to sort an already sorted array. Well, here are the results of comparing 1 million sorted float numbers in both heapsort and mergesort (quicksort won't sort either, because it'll exceed its maximum recursion depth):

I, for one, welcome our new sorting overlord!