Heap sort

Heap sort turns the list into a heap, a tree shape kept inside the list itself, where the largest value is always at the top. Then it takes the top off again and again. It is O(n log n) in every case and needs no extra list.

A tree inside a list

Read a list as a tree: position 0 is the top (the root), and the children of position i are at 2i + 1 and 2i + 2. Its parent is at (i − 1) // 2. No pointers are stored; the positions are worked out by arithmetic. This tree is always as full as possible, so its height is about log₂ n.

It follows that the root holds the largest value. The HEAP station covers heaps in full; this lesson uses just enough for sorting.

Sifting down

Suppose both subtrees below position i are already heaps, but a[i] may be too small. Swap it with its larger child, and repeat from there, until it is at least as big as its children or has none. This is sifting down. It moves down at most one level per swap, so it costs O(log n).

def sift_down(a, i, size):
    while True:
        big = i
        for c in (2 * i + 1, 2 * i + 2):
            if c < size and a[c] > a[big]:
                big = c
        if big == i:
            return
        a[i], a[big] = a[big], a[i]
        i = big

The sort

def heap_sort(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):   # build the heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]        # largest to the back
        sift_down(a, 0, end)               # fix the smaller heap

Building. Positions from n // 2 on have no children, so they are already tiny heaps. Sift down each other position, from the last parent back to the root. Each sift starts with heaps below it, as required. This takes O(n) in total, not O(n log n), because most positions are near the bottom and sift only a short way. The HEAP station proves it.

Sorting. Swap the root, the largest value, with the last value in the heap. That value is now in its final place. The heap is one shorter, and only the new root may be out of place, so one sift-down fixes it. n − 1 rounds of O(log n).

Heap sort against the others

• Like merge sort, it is O(n log n) in the worst case. Unlike merge sort, it needs only O(1) extra space.
• Like quick sort, it sorts in place. Unlike quick sort, it has no bad inputs.
• It is not stable, and it reads the list in a scattered order, which is slow on real memory. In practice quick sort is usually faster.

Heaps return in lesson 8 as another way to find the k smallest values.