Data Structures
Lessons · #7 of 11

Heaps & Priority Queues

Array-backed, log-time min — the engine of priority queues

Min-heap · array view ↔ tree view

array 
init

Try it: Insert and watch bubble-up swap pairs flash. Then extractMin — sift-down restores the invariant. Same array, two ways to look at it: row of cells and complete binary tree.

Why it matters

A heap is the same array-backed tree from the binary trees lesson — but with one extra rule that turns it into a constant-time min/max engine. When you need the maximum (or minimum) element quickly and repeatedly, heaps are the answer. They power priority queues, heap sort, and algorithms like Dijkstra's shortest path (which you saw in the graphs lesson's shortest-path mode).

The heap invariant

Two invariants, both must hold:

Heap invariants
Shape: the binary tree is complete — every level is full except possibly the last, which fills left-to-right. This lets us store the tree contiguously in an array, no holes.
Order (min-heap): for every node n, n.key ≤ key(child) for every child. (Flip to ≥ for max-heap.) The root therefore holds the minimum (or maximum).
What "preserve" means
Insert violates order temporarily at the leaf, then bubble-up restores it. Extract violates both temporarily (last leaf moves to root), then sift-down restores order while keeping the shape complete.

The idea

Imagine a tournament bracket where the winner always rises to the top. After each game, the better team moves up.

A heap is like that. In a max-heap, every parent is greater than its children. The root is always the maximum.

The clever trick: store it in an array! For node at index i:

Insert: Add at end, then "bubble up" - swap with parent while larger. Extract max: Remove root, put last element at root, then "sink down" - swap with larger child while smaller.

Both operations are O(log n) - just the height of the tree.

Key takeaways

Going deeper

Min-heap vs max-heap

A min-heap puts the smallest element at the root; a max-heap puts the largest. The mechanism is identical — only the comparison direction flips. Some languages default one way (C++ std::priority_queue is max; Python heapq is min) and you negate values to flip — heapq.heappush(q, -value). Always check.

The O(n) heapify proof

You'd think building a heap from n unordered elements costs O(n log n) — one O(log n) insert per element. But there's a better way: copy the array, then sift down from the middle index toward the root. Total cost is O(n), not O(n log n).

The proof is a beautiful geometric sum. A complete binary tree of n nodes has roughly n/2 leaves (depth 0 — no sifting needed), n/4 at depth 1 (at most 1 swap each), n/8 at depth 2 (at most 2 swaps), …, 1 root at depth log n (at most log n swaps). The total work:

work ≤ Σ (n / 2^(d+1)) · d   for d = 0..log n
     = (n/2) · Σ d / 2^d
     ≤ (n/2) · 2     since Σ d/2^d converges to 2
     = O(n)

Most nodes are near the bottom and sift down zero or one level. Only a vanishing fraction near the top do the full log n work. This is another flavor of amortized analysis — the worst case is concentrated at a few nodes, and they're few enough not to dominate.

Heap vs BST — when to pick which

Both give you O(log n) operations. Two practical differences decide which to use:

| Use case | Heap | BST | |---|---|---| | Repeated min/max extraction | ✓ O(1) peek, O(log n) pop | also O(log n) for min/max | | Range queries (find all > 50) | ✗ no order | ✓ O(log n + k) | | In-order traversal | ✗ | ✓ | | Memory overhead | array — no pointers | 2 pointers + value per node | | Constant factor | small (array, cache-friendly) | larger (pointer chasing) | | Build from n items | O(n) heapify | O(n log n) repeated insert |

Pick a heap when you only need min/max and never need order or range queries. Pick a BST (usually balanced) when you need ordered iteration or "find all keys in [a, b]". The graphs lesson's Dijkstra mode uses a heap because it always needs the next-cheapest frontier node, not the order of all frontier nodes.

Heap sort uses this: heapify in O(n), then extract max n times for O(n log n) overall — but with worse cache behavior than merge sort, so it's rarely the practical winner despite the matching asymptote.

Math details

Time Complexity
Insert: O(log n)
Extract max/min: O(log n)
Peek: O(1)
Heapify (build): O(n)
Array Index Formulas
left(i) = 2i + 1
right(i) = 2i + 2
parent(i) = lfloor(i-1)/2rfloor

Implementation

Heap Operations

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(4);  // Heap: max at top

let max = heap.pop();  // Returns Some(4)
let peek = heap.peek(); // Returns Some(&3)

When to Use

Practice

Three problems that show why the heap is your default tool for "give me the best/worst k things":

→ Browse all practice problems