Heap

What is a heap

A heap is a binary tree with one rule: every node is smaller than both of its children. What matters is what that leaves out — it says nothing about how a node compares to its sibling, its cousin, or anything not directly above or below it.

The rule pins down exactly one thing: the smallest value sits at the root, where you can read it without searching. Everything else is left vague, and that vagueness is what this article is about.

Look at that figure once more: 20 is deeper in the tree than 25, and smaller. In a Binary Search Tree that would be a defect. Here it is information the structure never promised to have.

The problem a Binary Search Tree couldn't solve

The previous article finished a structure that answers "where is this value" in guaranteed O(log n), keeps everything sorted, and supports range queries. It is excellent, and far more than you need if your only question is "what is the smallest one right now".

A balanced BST maintains a total ordering — every value's relationship to every other is implied by its position. That costs two pointers per node, a rebalancing pass on every write, and a scattered memory layout where each step of a lookup is a cache miss. If all you do is take the minimum and add new values, you are paying for a complete ranking and reading one entry from it. Worse, the minimum of a BST is its leftmost node, so even reading it is O(log n).

So: how much of the ordering can you throw away and still answer "what is the smallest"? Almost all of it.

Priority Queue is the ADT, heap is the structure

The two names get used interchangeably, and they are not the same kind of thing.

A Priority Queue is an abstract data type. It defines operations and their behaviour, and says nothing about memory: insert(value), extract-min(), and peek(). That is the contract. It is the queue from earlier in the series with the FIFO rule replaced — instead of the oldest item leaving first, the most urgent one does.

Notice there is no search, no iterate in order, no get the third smallest — a Priority Queue that cannot do those is not incomplete; those were never in the contract. Several concrete structures satisfy it, with very different cost profiles:

The two arrays are the extremes, and both are bad: one makes insertion free and extraction linear, the other does the reverse. The balanced BST is respectable at everything and best at nothing. The Fibonacci heap has the best asymptotics on paper and constant factors bad enough that almost nothing uses it. The binary heap is logarithmic on both writes and constant on the read, using a flat array and no pointers at all.

The invariant, and everything it does not say

The heap invariant is a statement about edges, not about the tree — for every node i, value[i] <= value[2i+1] and value[i] <= value[2i+2], and nothing else.

The BST invariant is a statement about entire subtrees: everything left is smaller, everything right is larger, all the way down. It constrains a node against n other values; the heap rule constrains it against two.

So a heap is wildly underdetermined. Seven distinct values form 80 legal min-heaps. Here are two of them.

Only the root matches, and that is not a coincidence — it is the only position the invariant determines. Fix a BST's shape and those seven values have one legal arrangement; a heap has eighty. That looseness is the source of the heap's speed: a structure that constrains less has less to repair when it changes.

It is also why you cannot read a heap in order. No single pass over the array yields sorted output, because the ordering information genuinely is not there. Getting it means extracting the minimum repeatedly, which costs O(n log n) and destroys the heap. Sorted iteration, range queries, "find the value nearest x" — none of it is available. That is the price, seen from the other side: the heap is fast because it never bought those.

Complete by construction

Because the invariant says nothing about which slot a value occupies — only about a slot's relationship to the two below it — the heap is free to choose its own shape. So it chooses the best one: it stays a complete binary tree, every level full except possibly the last, which fills left to right.

Nobody maintains that deliberately. It falls out of the two operations: insertion appends at the first free position, removal takes the last occupied one, and neither leaves a gap in the middle. And a complete tree, as the binary trees article showed, is exactly where the array representation is free:

That article warned that the same representation is catastrophic on a degenerate tree — 21 nodes in a chain would need two million slots. A heap can never be degenerate, so it lands in the free case every time.

Which makes the drawing above a lie of convenience: there is no tree. No nodes, no Left field, no Right field, no allocations. There is one contiguous slice of integers, and the tree is a way of thinking about the arithmetic. The diagram in the playground below is a view; the array under it is the structure.

Sifting up, and sifting down

Both write operations work the same way: put the value in the only slot that keeps the tree complete, then let it move along a single root-to-leaf path until the invariant holds. One value moves, at most log n levels.

Insert sifts up

Append at the end of the array — the first free slot — then swap with the parent while the new value is smaller. Inserting 5 above, it lands at index 7 as a child of 40.

Now 5 climbs. Smaller than 40, so they swap; smaller than 25, swap; smaller than 10, swap. Three comparisons, three swaps, and it stops at the root.

Only one root-to-leaf path was touched. Nothing in the right subtree was even read — the rest of the heap does not need to know an insertion happened.

Extract-min sifts down

The minimum is at the root, so reading it is free. Removing it leaves a hole at index 0, and the fix is to move the last element into the root and let it sink. At each level it compares against both children and swaps with the smaller one, stopping when both are larger.

Extracting from the heap we just built: 5 comes off the root, 40 moves up from the end, then sinks past 10 and past 25 to index 3.

Promoting the smaller child would be the obvious repair — it is already the next-smallest value, so the invariant would hold immediately — and it is the wrong move. It shifts the hole down a level rather than removing it, and repeating that leaves a gap in the middle of the last row. The tree stops being complete and the index arithmetic breaks: 2i+1 only points at a real child if every earlier slot is filled. Promoting the last element costs two extra comparisons per level, and in exchange the array stays dense forever.

Representing a heap in memory

There is no node type here, which is the shortest way to say everything above.

Count what is absent. No Node struct, no nil checks, no recursion, no allocation beyond the slice growing — Push and Pop are each one loop over an index. The most compact structure in the series, for exactly one reason: the invariant is weak enough that position can be computed instead of stored.

Try it yourself

The array is the structure and the tree is a view of it, so the playground shows both and moves them together. Insert a value and watch it land in the ghost slot at the end before it climbs; extract and watch the last element get promoted to the root and sink.

Insert a value smaller than everything present and it travels to the root, highlighting the only part of the structure that was touched. Then insert a large value and watch it stop after a single comparison — that is what the next section hinges on.

Building a heap from an array

Suppose you already have n values and want a heap. There are two ways, and the gap between them is the most quoted fact about heaps — and the one most often quoted without its qualifier.

Insert them one at a time, at O(log n) each, for O(n log n). Or put them all in the array as they are and sift down from the last internal node back to the root, which is O(n): sifting down is cheap where the nodes are numerous — half of all nodes are leaves and cannot move, a quarter can move one level, only the root can move log n — and that sum converges to a constant times n.

Three sift-downs turn that into [10, 25, 15, 30, 40, 50, 20], with every leaf skipped — on a large heap, half the array untouched. So far, so textbook: use the bottom-up build. That conclusion is right; the reasoning usually attached to it is not.

What measuring says

I instrumented both builds to count comparisons, on random input and on descending input — descending being the adversarial case for insertion, since every arriving value beats everything already in the heap and climbs to the root.

Comparisons per element. Read the columns, not the rows.

The bottom-up build is flat — 1.7 to 2.0 per element across a 256× range of sizes, and indifferent to whether the input is random or adversarial. That is what O(n) looks like when you measure it.

The insertion build is where the folklore misleads. On random input it costs 2.27 per element at n = 16,384, against a log₂ n of 14 — not n log n in any way you could detect, and barely worse than the bottom-up build. The reason is visible in the playground: a randomly chosen value is usually larger than its parent, so it stops after one comparison. The log n per insert is a worst case random data almost never reaches. On descending input it costs 12.00, tracking log₂ n to within two. There is the n log n, and it appears only when the input arrives sorted the wrong way.

Heapsort

Build a heap in O(n), then extract the minimum n times at O(log n) each. The output comes out sorted, for O(n log n) total.

The elegant part is that it needs no extra memory. Extraction shrinks the heap by one slot at the end of the array, and that slot is exactly where the extracted value goes — so the array sorts from the back forwards while the heap shrinks from the front. Genuine O(1) extra space, which mergesort cannot offer and quicksort manages only with care, plus a worst case no input degrades.

Almost nothing uses heapsort as its primary sort anyway, for two reasons.

It is not stable. Two equal values can come out in the opposite order to the one they went in, because the sift swaps them across the array with no regard for where they started. If you sort records by one field and expect ties to keep their previous order, heapsort silently breaks that.

Its memory access pattern is hostile. Every sift down jumps from index i to 2i+1, so the further into a large array you go the further apart consecutive accesses are. Quicksort scans linearly and is far friendlier to the cache — enough to win in practice despite its O(n²) worst case.

So most standard libraries ship introsort: quicksort, switching to heapsort if the recursion passes 2 log n levels. Heapsort is in your language's sort function — as the parachute, not the engine.

Common operations and their costs

The top four rows are why heaps exist; the bottom two are what they cost. Read the fourth against the sixth: a heap builds in linear time precisely because it never reaches sorted order — and that same shortfall is why getting sorted output back out costs O(n log n). One trade, seen twice.

Heaps in the real world

Schedulers and timers

Go's own runtime keeps each processor's pending timers in a min-heap, so "which fires next" is a constant-time read. It uses a 4-ary heap rather than a binary one — four children per node, so the tree is shallower and a sift down does more comparisons at fewer levels, which suits a cache. Python's asyncio schedules its callbacks with heapq. Any system with scheduled work has this shape — cron, a job queue, a rate limiter, a discrete-event simulation, a game engine's timed events. Many things waiting, one question, asked constantly.

Top-k without sorting

To find the 10 largest values in a stream of a billion, keep a min-heap of size 10: for each new value, compare against the root, and if it is larger replace the root and sift down. You end up holding the top 10 in O(n log k) time and O(k) space, without ever storing the stream.

The counter-intuitive part is using a min-heap to track maxima. The root being the smallest of your ten best is exactly what you need, because that is the one to evict.

Shortest paths

Dijkstra's algorithm and A* both work by repeatedly taking the closest unvisited node, which is a priority queue by definition. This is the most common place a working programmer meets a heap deliberately, and where graph algorithms will pick the story up later.

Your language already ships one

Go has container/heap, which supplies the sift logic once you provide five methods: Len, Less and Swap, plus a Push and Pop that the package calls on your slice — not the ones you call yourself, which is the detail that trips people up. Python has heapq, over a plain list. Java has PriorityQueue, C++ has priority_queue, and Rust has BinaryHeap — a max-heap, so a min-heap means wrapping values in Reverse.

When Heaps fall short

There is no search. Finding an arbitrary value is O(n), because the invariant offers no direction to go at any node. Needing "is x in here" as well as "what is the minimum" means a second index alongside the heap.

Updating an arbitrary element needs help. Decrease-key — lowering a value's priority — is what Dijkstra actually wants, and it is O(log n) if you already know the element's index. Finding that index is the O(n) search above. Real implementations keep a separate map from value to index and update it on every swap, which is fiddly and the most common source of bugs in hand-written heaps.

Only one end is fast. A min-heap answers "what is the smallest" in O(1) and "what is the largest" in O(n) — the maximum is somewhere among the leaves. Needing both means a min-max heap, or two heaps kept in balance, which is the standard trick for a running median.

No ordering, no ranges. Everything the previous two articles offered — sorted iteration, BETWEEN, successor and predecessor — is gone. If you need those and fast minimum access, a balanced BST gives both.

Merging two heaps is slow. Combining two binary heaps of size n means rebuilding, at O(n); binomial, pairing and leftist heaps are designed for it and merge in O(log n).

Summary

A heap is what you get when you keep only the part of the ordering that answers one question:

• The invariant is only parent against child — nothing between siblings, nothing between subtrees, which is why seven values form 80 legal heaps and only the root is pinned down
• Weak enough to be shapeless, so the shape can be chosen — the operations keep the tree complete without trying, and that is exactly where the array representation costs nothing
• There is no tree — one contiguous slice, with 2i+1, 2i+2 and (i−1)/2 replacing every pointer
• Insert sifts up, extract sifts down — one value moves along one root-to-leaf path, at most log n levels, touching nothing else
• The last element is promoted on extract, not the smaller child, because that is the only choice that leaves no hole
• Bottom-up building is O(n) — under 2 comparisons per element regardless of size or input order, while insertion degrades to log n only on adversarial input
• Heapsort is in-place and guaranteed, and not stable — which is why it ships as introsort's fallback rather than as the default sort

The insight to carry forward is that this is the first structure in the series that got faster by promising less. Every earlier article added a constraint to buy a capability: ordering to enable search, balance to bound the height. The heap goes the other way and comes out with a constant-time minimum, a linear-time build and no pointers at all. When a structure feels expensive, the productive question is often not how to speed it up but which of its guarantees you were never using.

That closes the tree series. It opened with a tree as nothing more than a way to give a node more than one next; it turned out to be the shape underneath ordered maps, database indexes, schedulers and priority queues. The next article drops the last two restrictions — one parent per node, no cycles — and asks what is left when a node can point at anything at all.