The heap property

Many programs only ever need the smallest item: the next event in a simulation, the most urgent task, the closest unvisited place on a map. A heap is built for exactly that job. It finds the smallest item in O(1) and adds or removes an item in O(log n), and it is stored in a plain list.

A structure for the smallest value

Compare the simple choices for a collection where you keep adding items and taking out the smallest one:

A balanced tree matches the heap’s cost, but it keeps the whole collection in order, which is more than this job needs. A heap keeps only enough order to know the smallest item. That makes it simpler, smaller and faster in practice.

The heap rule

A binary heap is a binary tree with two properties. The first is about its shape: it is a complete tree, meaning every level is full except perhaps the last, and the last level is filled from the left with no gaps. The second is about its order:

From the rule, the root holds the smallest value. Proof: take any node and walk up from it to the root. Each step goes to a parent, whose value is at most the child’s, so the values never grow on the way up. So the root is at most every node.

A max-heap uses the opposite rule (every parent is at least its children), so its root holds the largest value. Heap sort in SORT-4 used a max-heap. This station uses min-heaps, as Python’s heapq does.

A tree stored in a list

Because the tree is complete, there is no need for nodes and links. Write the values level by level, left to right, into a list. The positions then give the shape. Step through the figure:

• The root is at position 0.
• The children of position i are at 2i + 1 and 2i + 2, if those are less than n.
• The parent of position i is at (i - 1) // 2 (// divides and rounds down).
• Positions n // 2 to n − 1 are leaves: the second half of the list has no children.

Why do these formulas work? Level d holds 2^d positions (d twos multiplied together; 2⁰ is 1), starting at position 2^d − 1. The node at position i has i nodes before it in the list; its children come right after the children of all those nodes, two each, so the first child lands at 2i + 1.

A complete tree with n nodes has height log₂ n rounded down: 3 for 8 to 15 nodes, 19 for a million. Every operation in this station walks one path, so this height is what makes them fast.

What a heap does not tell you

A heap is much weaker than a sorted list. Siblings are in no order: in the figure, 3 is to the left of 2. And a value deep in one branch can be smaller than a value higher up in another branch: in the heap [1, 5, 2, 6, 7, 3], 3 is two levels down but smaller than 5, which is one level down. So a heap cannot:

• find an arbitrary value faster than O(n): the rule rules out very little;
• list the values in order without taking them out one by one. The second smallest is one of the root’s two children, but the third smallest could be a child of either of them, and the choices grow further down.