Heaps and priority queues

A balanced tree keeps every key in its correct place relative to every other, and a great many problems never ask a question that needs it.

A scheduler asks for the next job to run, a simulation for the next event to happen, a network router for the highest-priority packet, a compressor for the two least frequent symbols. Each of those is the same question, "which is smallest", asked repeatedly while new items arrive. Maintaining a total order to answer it is paying for an invariant that is never queried. This lesson builds the structure that answers exactly that question and nothing else, and the saving turns out to be large enough to matter.

The abstract operation, and the weaker invariant

The interface is the priority queue: insert an item with a priority, and extract the item of smallest priority. Optionally peek at the smallest without removing it, and change an item's priority.

An unsorted array does insertion in $Θ (1)$ and extraction in $Θ (n)$ , since finding the minimum means scanning. A sorted array reverses that, $Θ (n)$ to insert and $Θ (1)$ to extract. A balanced tree does both in $Θ (\log n)$ and throws in everything else. The question is whether the restricted interface can be served more cheaply than the general one.

It can, because the ordering it needs is weaker. A binary min-heap is a binary tree satisfying one condition: every node's key is less than or equal to both of its children's keys. That is all. Nothing relates the two children to each other, nothing relates the left subtree to the right, and the same set of keys admits an enormous number of valid heaps.

What survives is exactly the one thing wanted. By transitivity, the root is less than or equal to every key in the tree, so the minimum is at a known position and reading it costs nothing.

No pointers at all

The second condition is structural. A heap is a complete binary tree: every level is full except possibly the last, which is filled from the left. That shape is rigid enough to be described without pointers.

Number the nodes in level order, starting from 0 at the root. Then the children of node $i$ are at $2 i + 1$ and $2 i + 2$ , and the parent of node $i$ is at $⌊ (i - 1) / 2 ⌋$ . Navigating the tree is arithmetic, exactly as indexing an array was arithmetic in the third lesson, so the heap is a plain array with no node objects, no allocation per element, and no pointer overhead. For a million 8-byte keys that is 8 MB against the 24 MB a binary tree with two child pointers would need, and the array is contiguous, so a level-order sweep is a sequential scan.

Completeness also fixes the height at exactly $⌊ \log_{2} n ⌋$ , with no balancing machinery required. A heap cannot degenerate, because its shape is not a consequence of the data at all.

Example. In a heap held in an array of 9 elements, indices 0 to 8, what are the children of index 1, the parent of index 7, and the height?

The children of index 1 are at $2 (1) + 1 = 3$ and $2 (1) + 2 = 4$ . The parent of index 7 is at $⌊ 6 / 2 ⌋ = 3$ . The height is $⌊ \log_{2} 9 ⌋ = 3$ , and indeed index 8 sits at depth 3 with parent 3, grandparent 1 and great-grandparent 0.

Now you. In a heap of 100 elements, what are the children of index 40, the parent of index 40, and which indices are leaves?

Answer

The children of 40 are at 81 and 82, and its parent is at $⌊ 39 / 2 ⌋ = 19$ . A node is a leaf when it has no child inside the array, so when $2 i + 1 \geq 100$ , meaning $i \geq 49.5$ : indices 50 to 99 are the leaves, which is half the array. That half of all nodes are leaves is the fact the linear-time build below depends on.

Insert and extract

Both updates work by moving one element along a single root-to-leaf path, repairing the heap property as they go.

To insert, place the new key at the end of the array, which keeps the tree complete, and then sift up: while the key is smaller than its parent, swap them. Each swap moves the key one level up, so the cost is at most $⌊ \log_{2} n ⌋$ comparisons and swaps. The property is restored because the only node that could have violated it was the new one relative to its ancestors, and swapping puts a smaller key above a larger one without disturbing either's other child.

To extract the minimum, take the root, move the last element of the array into the root position, shrink the array by one, and then sift down: compare the key with its two children, swap with the smaller of them if either is smaller, and repeat. The cost is again at most $⌊ \log_{2} n ⌋$ levels, at two comparisons per level. Swapping with the smaller child is essential: swapping with the larger one would put it above its sibling and break the property immediately.

Example. Sift-down turns an arbitrary array into a heap. Apply it to 5, 13, 2, 25, 7, 17, 20, 8, 4, working from the last internal node backwards.

With nine elements the last internal node is index 3, holding 25, whose only child is 4 at index 8, so they swap. Index 2 holds 2, smaller than both 17 and 20, so nothing moves. Index 1 holds 13; its children are now 4 and 7, so 13 swaps with 4 and then, at index 3, swaps with its child 8. Index 0 holds 5; its children are 4 and 2, and 2 is smaller, so they swap, after which 5 is smaller than 17 and 20 and stops. The array is now 2, 4, 5, 8, 7, 17, 20, 13, 25, which satisfies the heap property everywhere, and it took four swaps.

Now you. Do the same for 9, 4, 7, 1, 8, 3, 6, 2, 5.

Answer

Index 3 holds 1, smaller than its child 2, so nothing moves. Index 2 holds 7 with children 3 and 6, so 7 swaps with 3. Index 1 holds 4 with children 1 and 8, so 4 swaps with 1, then at index 3 swaps with its child 2. Index 0 holds 9, which sinks past 1, then past 2, then past 4, three swaps. The result is 1, 2, 3, 4, 8, 7, 6, 9, 5, using six swaps. Note that the final array is not sorted and is not required to be.

Building a heap costs $Θ (n)$ , not $Θ (n \log n)$

Inserting $n$ keys one at a time costs $O (n \log n)$ . The build just performed does better, and the reason is worth doing properly because the same style of argument recurs.

Sift-down from every internal node, working backwards from index $⌊ n / 2 ⌋ - 1$ to 0. Each call is correct because both subtrees are already heaps by the time the call is made, which is what processing in reverse index order guarantees.

The naive bound is $n / 2$ calls each costing $\log_{2} n$ , giving $O (n \log n)$ . That over-counts badly, because almost every node is near the bottom and a sift-down from near the bottom has almost nowhere to go. At height $h$ above the leaves there are at most $⌈ n / 2^{h + 1} ⌉$ nodes, and each costs $O (h)$ . So the total is

\sum_{h = 0}^{⌊ \log_{2} n ⌋} \frac{n}{2^{h + 1}} h = \frac{n}{2} \sum_{h = 0}^{\infty} \frac{h}{2^{h}}

and $\sum_{h \geq 0} h / 2^{h}$ converges to exactly 2, so the whole sum is at most $n$ . Building a heap of a million elements costs about a million swaps, not twenty million. Half the nodes are leaves and cost nothing at all, a quarter can move one level, an eighth two levels, and the series converges before the height ever matters.

Heapsort

The heap gives a sort immediately: build a max-heap, then repeatedly swap the root with the last element of the active region, shrink the region by one, and sift down. The largest element lands at the end, the next largest just before it, and after $n - 1$ rounds the array is sorted in ascending order, in place, with no recursion and no extra array.

Published by J. W. J. Williams in 1964, with the linear-time build added by Robert Floyd the same year, heapsort was the first sort to be simultaneously in place and guaranteed $Θ (n \log n)$ . Mergesort has the guarantee and needs $Θ (n)$ memory; quicksort is in place and has no guarantee; heapsort has both.

It is nevertheless the slowest of the three in practice, by a factor of two or so, for two honest reasons. It makes about $2 n \log_{2} n$ comparisons, roughly 39.9 million for a million elements against mergesort's 18.9 million and quicksort's 24.8 million, because each sift-down level costs two comparisons rather than one. And its access pattern is the opposite of cache-friendly: sifting down from index $i$ jumps to $2 i + 1$ , then $4 i + 3$ , striding further with every level, so the deep levels of a large heap miss the cache on every step. This is why its usual role is not as a sort in its own right but as introsort's fallback, guaranteeing the worst case while quicksort handles the ordinary one.

Top $k$ without sorting

The heap answers a common question far more cheaply than sorting does. To find the $k$ largest of $n$ items, keep a min-heap of size $k$ : push the first $k$ items, then for each remaining item compare it with the heap's root, and if it is larger, replace the root and sift down. At the end the heap holds the $k$ largest.

The cost is $O (n \log k)$ time and $Θ (k)$ memory, and neither $n \log n$ nor $Θ (n)$ appears. The memory is the more important half: the whole input never has to be held at once, so this works on a stream that does not fit in memory.

Example. Find the 100 largest values among a billion. Compare with sorting.

The heap method costs about $10^{9} \times \log_{2} 100 = 10^{9} \times 6.64 = 6.6 \times 10^{9}$ operations and holds 100 items. Sorting costs about $10^{9} \times \log_{2} 10^{9} = 3.0 \times 10^{10}$ comparisons and holds all $10^{9}$ items, which at 8 bytes each is 8 GB. That is 4.5 times fewer operations and ten million times less memory, and the comparison flatters sorting by ignoring that 8 GB may not exist.

Now you. Find the 10 largest of a million.

Answer

$10^{6} \times \log_{2} 10 = 10^{6} \times 3.32 = 3.3 \times 10^{6}$ operations against $10^{6} \times 19.93 = 2.0 \times 10^{7}$ for a sort, a factor of six, with 10 items held instead of a million. Quickselect from the eighth lesson would also do this in $O (n)$ expected time, and is the better choice when the data is already in an array in memory and may be rearranged; the heap wins when it is arriving as a stream.

Variants, and what comes next

Two extensions matter later. A $d$ -ary heap gives each node $d$ children instead of two, which makes the tree shallower, so sift-up costs $\log_{d} n$ , at the price of $d - 1$ comparisons per sift-down level. Since Dijkstra's algorithm does far more decrease-key operations, which sift up, than extractions, a 4-ary heap is measurably faster there.

Decrease-key is the operation of lowering an item's priority in place, which is a sift-up from wherever it sits and therefore $O (\log n)$ , but it requires knowing where the item is: a heap has no lookup, so a separate index from item to array position must be maintained alongside. The Fibonacci heap of Fredman and Tarjan (1984) reduces decrease-key to $O (1)$ amortised, which improves Dijkstra's theoretical bound to $O (E + V \log V)$ ; its constants are large enough that ordinary binary heaps win on all but enormous graphs, and it is a case where the better complexity is genuinely the worse choice.

The course now has a structure for every shape of data it has met: arrays and lists for sequences, hash tables for exact lookup, balanced trees for order, heaps for priority. Each of them stores a collection whose elements have no relationships beyond their keys.

A great deal of real data is not like that. Roads connect towns, functions call functions, packages depend on packages, people know people. The relationships are the data, and none of the structures so far can represent them, let alone answer questions about paths through them. The next lesson introduces the object that can, and finds that this heap is exactly what its shortest-path algorithms will run on.

The abstract operation, and the weaker invariant

No pointers at all

Insert and extract

Building a heap costs Θ(n), not Θ(nlogn)

Heapsort

Top k without sorting

Variants, and what comes next

Building a heap costs $Θ (n)$ , not $Θ (n \log n)$

Top $k$ without sorting