Heaps & Priority Queues

A heap is the array-backed binary tree that powers every "what's the smallest / largest / next thing?" question in real systems: job schedulers, Dijkstra's algorithm, Huffman encoding, event-loop timers, and the streaming top-k trick that lets you find the 100 largest values in a billion-element stream using 800 bytes of memory.

The magic is all in the invariant and the layout. Two pieces. That's the whole data structure.

The invariant

A min-heap is a complete binary tree where every parent is ≤ both of its children. (Flip the inequality for a max-heap.) That's it. Weaker than a sorted tree — siblings can be in any order; cousins can be in any order; only the parent-child pair is constrained — but strong enough that the minimum is guaranteed to sit at the root. Peek the root: O(1). Remove it and restore the invariant: O(log n).

A heap is not a sorted structure. If you flatten a heap into an array you won't get a sorted list. You'll get a list where every prefix is locally ordered but globally reshuffled. That's the cost of the cheap O(1) min.

The array layout

Here's the trick that turns "binary tree" into "plain array with some index math." In a 0-indexed array of size n, for any node at index i:

• Left child lives at 2i + 1
• Right child lives at 2i + 2
• Parent lives at floor((i - 1) / 2)

No pointers. No malloc. No fragmentation. A heap is a single contiguous array; navigation between parent and child is pure arithmetic. This is why heaps are blindingly fast in practice — they pack tightly into cache lines and every operation is a handful of integer multiplies and comparisons.

You'll see 1-indexed variants too (CLRS uses them because the math is slightly prettier: parent = i/2, children = 2i and 2i + 1). Always confirm which convention a library uses before you start debugging.

Push = sift up

To insert v:

1. Append v to the end of the array (the next open leaf slot).
2. Compare it to its parent. If v < parent (min-heap), swap.
3. Repeat from the new position. Stop when v ≥ parent or you hit the root.

The swapping walks v up the tree toward the root. Depth of a binary tree with n nodes is ⌊log₂ n⌋, so push is O(log n) in the worst case.

Pop = move-and-sift-down

Removing the minimum looks weird at first:

1. Take the root's value (that's your return value).
2. Move the last element into the root slot.
3. Sift it down — compare to the smaller child, swap if the parent is larger, repeat.

The "move the last element to the top" step looks destructive because you're placing a probably-large value at the root. But it preserves the completeness of the tree (you never leave a gap in the middle), and the sift-down walks the displaced element back to its correct level. Again O(log n).

Heapify = build heap in O(n), not O(n log n)

You might assume "build a heap from n values" costs n × push = O(n log n). It doesn't. Floyd's build-heap algorithm runs sift-down from floor(n/2) - 1 (the last internal node) down to index 0, and the total work is O(n).

Why? Because the amortised cost depends on the height of each node — and most nodes in a binary tree are leaves or near-leaves. Half the nodes are leaves (height 0, zero sift-down work). A quarter are at height 1 (one swap max). An eighth at height 2. The sum Σ (n / 2^(h+1)) × h over all heights converges to a constant multiple of n. The proof is three lines of algebra once you've seen it; the takeaway is: repeatedly pushing is slower than batching heapify.

Priority queue = heap's killer app

A priority queue is any data structure that supports "peek the highest-priority element" and "remove the highest-priority element" efficiently. Heaps are the canonical implementation because they give you both in O(log n) with trivial constants. Real uses:

• Job schedulers — run the earliest-deadline task first.
• Dijkstra's shortest-path algorithm — always expand the closest unfinished node.
• Huffman coding — merge the two lowest-frequency symbols, repeat.
• Event-loop timers — the next timeout is always the smallest future time; heap gives you O(log n) setTimeout and O(log n) clearTimeout.
• A pathfinding in games* — expand the node with the lowest f = g + h score next.
• Event simulators — process events in timestamp order regardless of insertion order.

The streaming top-k trick

This is the pattern that makes heaps feel magical. Problem: you have a billion values streaming past and you want the 100 largest. You can't sort the stream (O(n log n) time, but also O(n) space you don't have). Instead:

1. Keep a min-heap of size k.
2. For each incoming value v:
   • If the heap has fewer than k elements, push v.
   • Otherwise, peek the root. If v > root, replace the root with v and sift down. If v ≤ root, skip.
3. At the end, the heap contains the k largest values.

Total work: O(n log k) — the same log n factor you'd pay for a full sort, but with k (small, fixed) instead of n (huge, streaming). Memory: O(k). That's how the top-100 of a billion values fits in 800 bytes.

Counterintuitive bit: you keep the largest values using a min-heap. The reason is exactly the peek-and-evict pattern — the min-heap's root is your easy-to-evict "weakest kept" value. Anything smaller than the root is by definition too small to beat what you already have, so you skip it in O(1).

Real standard libraries

Every mainstream language ships a heap; the defaults differ:

Language	Module	Default
Python	heapq	min-heap (list, free functions)
Java	java.util.PriorityQueue	min-heap
C++	std::priority_queue	max-heap
JavaScript	— (no stdlib)	use a library or hand-roll
Go	container/heap	interface you implement
Rust	std::collections::BinaryHeap	max-heap

The C++ / Rust defaults being max-heap and the Python / Java defaults being min-heap is the most common footgun. Read the docs. For a max-heap in Python, negate your keys on the way in and out.

Gotchas

• 0-indexed vs 1-indexed math. 0-indexed: parent = (i-1)/2, children = 2i+1/2i+2. 1-indexed: parent = i/2, children = 2i/2i+1. Mixing them produces silent corruption.
• Heap ≠ sorted. Iterating the array gives you heap order, not sorted order. If you need sorted output, repeatedly pop — that's heapsort, which is O(n log n).
• Removing an arbitrary element requires index tracking. Heaps support O(log n) pop of the root but have no fast "remove a specific value" operation unless you maintain a value → index map. Keep that in mind for Dijkstra-style decrease-key patterns.
• Duplicates are allowed. There's no uniqueness constraint; [1, 1, 1] is a perfectly valid heap.

Playground

Pick an operation — push, pop, heapify, or topK — and watch the array reshape itself frame by frame. The cells highlighted in var(--color-accent) are the two indices the algorithm is comparing or swapping. Try heapify on the reverse-sorted input [9, 8, 7, 6, 5, 4, 3, 2, 1] and count the sift-down steps: the linear cost is visible.

Visualizer

The Heap Tree panel shows the tree and the array side-by-side for the same data. Both views highlight the same two indices every frame — click through and you can see how "swap nodes in the tree" corresponds to "swap cells in the array." The dashed warning line is the swap motion arrow. Watching the tree rebalance is the fastest way to internalise that a heap is just an array with parent-child index math bolted on.