Building a heap in O(n)

Given a whole list at once, you could push its values into a heap one at a time, for O(n log n) work. There is a better way: fix the list from the bottom up, in place, in O(n). The proof is a short sum.

Two ways to build

One at a time. Treat the start of the list as a heap that grows: for each position i from 1 to n − 1, sift position i up. Each sift costs up to the depth of the node, and most nodes are deep, so this costs O(n log n) in the worst case (a decreasing list, where every value moves up to the root).

Bottom up. The second half of the list, positions n // 2 to n − 1, are leaves, and a single value is already a heap. Now walk backwards from the last parent, position n // 2 - 1, to the root, and sift each position down.

def heapify(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)

Step through both on the same list, 8 down to 1, and compare the comparison counts.

Why bottom-up works

That holds at the start, because the children of the last parent are leaves. Sifting position i down then makes the subtree under i a heap: it is exactly the situation of a pop, where the root is out of place and both subtrees below it are heaps. Positions are handled from the end backwards, so the children of i (at 2i + 1 and 2i + 2, which are bigger numbers) are always done first. When position 0 is done, the whole list is a heap.

Adding up the work

A sift down from a node costs at most its height: the number of levels below it. The reason is that most nodes have a small height. In a complete tree of n nodes:

• about n/2 nodes are leaves (height 0) and cost nothing;
• about n/4 have height 1, about n/8 have height 2, and in general about n/2^h+1 have height h (that is, n halved h + 1 times).

So the total number of swaps is at most:

  n/4·1 + n/8·2 + n/16·3 + ...
= n · (1/4 + 2/8 + 3/16 + ...)
= n · 1

The series in brackets adds up to exactly 1. One way to see it: write 2/8 as 1/8 + 1/8, 3/16 as 1/16 + 1/16 + 1/16, and so on, then regroup into the sums 1/4 + 1/8 + 1/16 + … = 1/2, 1/8 + 1/16 + … = 1/4, 1/16 + … = 1/8, which together make 1/2 + 1/4 + 1/8 + … = 1.

The one-at-a-time build loses because it does the opposite: the many nodes near the bottom are the ones that may travel far (up to the root), and the few nodes near the top travel little.

Where it is used

• heapq.heapify(a) does exactly this, in place, in O(n). Use it instead of pushing values one by one when you have them all at the start.
• Heap sort (SORT-4) starts with this build, then pops n times. The build is O(n); the pops are O(n log n).
• Getting the k smallest values of a list: heapify, then pop k times, is O(n + k log n) (lesson 5).