Binary Heap Visualizer

Most data structures that behave like trees are built like trees. Each node is a small record, and inside it sit the addresses of its children. Follow the addresses and you walk the tree.

The binary heap behaves like a tree and is built like a list. There are no records and no addresses. There is one array, and the tree exists only in the arithmetic you do on its positions. The idea dates from 1964 and is still one of the neatest in the field.

A tree you can lay flat

The trick depends on a restriction. A heap is not allowed to be any shape it likes. It must be a complete binary tree: every level is full except possibly the deepest, and that last level is filled from the left with no gaps. A tree like that has only one possible outline for a given number of nodes, so the outline carries no information and does not need to be stored.

Read such a tree level by level, left to right, and write the keys into an array in that order. Now the family relations become sums. Counting cells from 0, the children of cell i are cells 2i + 1 and 2i + 2, and the parent of cell i is cell floor((i - 1) / 2). Textbooks that count from 1 write the same thing as 2i, 2i + 1 and i / 2, which is tidier. Code that counts from 0 uses the first form, and the Python library says outright that it does so because the language does.

That is the shape rule. The order rule is just as short. In a min-heap no key is smaller than its parent. In a max-heap no key is larger than its parent. Nothing is promised about brothers, sisters or cousins, and an array in heap order usually looks half shuffled to the eye.

The weakness of the promise is the point. A sorted array promises everything and is expensive to keep sorted. A heap promises one thing, that the best key is at the root in cell 0, and it can keep that promise cheaply while keys come and go.

Up and down

Two small repairs do all the work, and both follow a single path between the root and a leaf.

To insert a key, put it in the first free cell, which is the next leaf. The shape is still right, but the newcomer may beat its parent. Compare the two. If the newcomer wins, swap them and ask the same question one level higher. This is sifting up. It ends when the key meets a parent that outranks it, or when it reaches the root.

To take the best key out, lift it from the root. That leaves a hole at the top and one cell too many at the bottom, so move the last key into the root. Now the shape is right and the order is almost certainly wrong. Compare the two children with each other, then compare the better one with the misplaced key. If the child wins, swap and repeat from the child’s cell. This is sifting down.

Each repair is bounded by the height of the tree, and the height of a heap holding n keys is the whole part of the base two logarithm of n. A thousand keys make a tree nine levels deep below the root, a million make nineteen. Sifting up costs at most one comparison per level. Sifting down costs up to two, because it must first find out which child to consider.

Changing a key in the middle, or deleting one, is the same pair of repairs started from a different cell. If the new key outranks its parent it sifts up, and otherwise it sifts down. Only one of the two can ever be needed.

The build that should cost more

Suppose you already have all the keys and want them in heap order. The obvious way is to insert them one at a time. J. W. J. Williams, who published the heap and heapsort together in 1964, built his heap this way. Each insertion can climb the full height, so the worst case grows as n times the logarithm of n.

Later the same year Robert W. Floyd published a better way. The dictionary kept by the United States standards institute puts it plainly: Williams stated the idea, and Floyd gave an efficient implementation close to the one in use today. Floyd’s build ignores insertion entirely. It treats the unordered array as a tree that is already the right shape, then starts at the last node that has a child and works backwards to the root, sifting each node down.

This looks like the same amount of work, since it also runs a logarithmic repair for about half the nodes. It is not, and the reason is where the nodes are. Half of the nodes in a complete tree are leaves and need nothing. A quarter sit one level above the leaves and can sink at most one step. An eighth can sink two. Only the root can travel the whole height. Insertion has it the other way round: the crowded bottom level is exactly where its longest climbs happen.

Add it up level by level and the total number of swaps comes to less than n, however large n is. The published worst case for the comparisons is exact: 2n, minus twice the number of 1 bits in n written in binary, minus the number of trailing 0 bits. That is always under 2n. Building a heap is linear.

Here is a case small enough to follow by hand. Take the twelve keys 42, 17, 8, 93, 56, 23, 71, 5, 64, 30, 12, 88 and build a min-heap bottom-up. Six of the twelve are leaves. Three nodes have height one, two have height two, and the root has height three, so the most swaps possible is 3 + 4 + 3 = 10. The formula allows 18 comparisons. The real run uses 17 comparisons and 6 swaps and leaves the array as 5, 12, 8, 17, 30, 23, 71, 93, 64, 42, 56, 88.

Insertion on those twelve keys happens to take 15 comparisons, two fewer. That is not a mistake. On a kind input, insertion is cheap, because most newcomers lose their first comparison and stay put. The gap opens on an unkind one. Give a min-heap 127 keys in descending order, so that every new key is the smallest so far and must climb to the root. Bottom-up needs 240 comparisons, which is exactly its worst case for that size. Insertion needs 642. That is 240 against 642 for the same keys and the same finished heap property, and the difference keeps widening as the array grows.

Sorting without a second array

Heapsort falls out of the two repairs almost for free. Build a max-heap. The largest key is now in cell 0. Swap it with the last cell of the heap, declare the heap one cell shorter, and sift the new root down. The largest key is in its final place and the heap has reformed in front of it. Repeat until the heap is empty.

The sorted keys grow from the back of the same array the heap is shrinking in. That is what in place means: the method needs no second array, only room for one key during a swap. It also has no bad day. Its worst case grows as n times the logarithm of n, the same as its typical case, which is why some quicksort implementations keep it as a fallback for inputs that would otherwise go wrong.

What heapsort gives up is stability. A stable sort keeps items with equal keys in the order they arrived. Sort a class list by name and then by section with a stable method, and each section is still in name order. Heapsort makes no such promise. Its swaps carry keys across the whole array, and two equal keys can easily pass one another on the way. When the order of equals matters, the usual remedy is to add the original position to the key as a tie-breaker.

Where the queue with priorities shows up

A heap is the usual way to build a priority queue, which is a collection that hands back its most urgent item first. Several standard libraries ship one as a binary heap. Rust’s is a max-heap. Python’s is a min-heap kept in an ordinary list.

The uses are less glamorous than the name. A simulation keeps its future events in one, ordered by the time they are due, and repeatedly pulls the earliest. Schedulers do the same with tasks. Dijkstra’s shortest path method and Prim’s spanning tree method both ask, again and again, for the nearest vertex not yet settled. Huffman’s coding method asks for the two rarest symbols. Merging many sorted files into one keeps the head of each file in a heap and always takes the smallest.

It is worth being clear about what a heap will not do. It cannot find an arbitrary key without looking through the array, and it cannot list its keys in order without taking them out one by one. And on large arrays the parent and child of a node sit far apart in memory, which costs time that the comparison counts do not show.

Within those limits it is hard to beat. One array, two short loops, and the next thing you need is always in cell 0.