Heaps & Priority Queues

The 10-second versionCopy Anchor Link

A priority queue is an abstraction: you throw items in, and whenever you ask for the next one you get the most important item, not the oldest. The binary heap is the classic way to build one. It's a complete binary tree — every level full except maybe the last — squeezed into a flat array, with one rule: each parent is smaller than its children (a min-heap; flip it for a max-heap). That single rule keeps the minimum parked at index 0, so peek is O(1) and insert/remove are O(log n). No sorting, no pointers, no wasted memory.

Why this existedCopy Anchor Link

Suppose you keep getting items and you keep needing the smallest one — a scheduler picking the next task, a router choosing the next packet, a simulation advancing the next event. The obvious approaches all hurt:

• Unsorted array: inserting is O(1), but finding the min means scanning everything, O(n).
• Sorted array: the min is right there at index 0, but inserting a new item means shifting it into place, O(n) per insert.
• Balanced BST: both are O(log n), but you pay for pointers, rotations, and a node per element.

What people wanted was a structure with O(log n) insert and O(log n) extract-min, using almost no memory. In 1964, that structure arrived.

• 1964 — J. W. J. Williams publishes the binary heap together with heapsort, a sorting algorithm built directly on it.
• 1964 — Robert Floyd improves the heap with an in-place sift-down and an O(n) bottom-up heapify — no extra storage needed to build a heap.
• 1973 — Knuth's The Art of Computer Programming, Volume 3 treats heaps and priority queues as core material, cementing them in the canon.
• Since — every language ships one, and graph algorithms lean on it.

Why it mattered: a priority queue turns "find the extreme" from a repeated O(n) scan into a maintained O(1) peek. Algorithms like Dijkstra and A* become practical only because of it.

Inside the inventor's headCopy Anchor Link

Williams wasn't staring at a scheduler. He was trying to sort. The obvious sort is selection sort: repeatedly find the biggest remaining element and move it to the end. The cost is all in the finding — scanning n items, n times.

So he asks a sharper question: what if, instead of searching for the max each round, I keep a structure where the max is always already at the top? That's the pivot.

The second insight — the one that makes it elegant — is the shape. A complete binary tree fits perfectly in a flat array: parent i has children 2i+1 and 2i+2, and child i has parent (i-1)/2. So you get a tree's O(log n) height with an array's cache-friendly, pointer-free storage. You keep it a tree only in your head.

Watch the two approaches for "get me the maximum":

// Naive: to get the max, scan the whole array every single time.function findMax(a) {  let best = a[0];  for (const x of a) if (x > best) best = x;  // O(n) per call  return best;}

// Max-heap sift-up: restore the heap property after an insert.function siftUp(a, i) {  while (i > 0) {    const parent = (i - 1) >> 1;    if (a[parent] >= a[i]) break;         // property holds, stop    [a[parent], a[i]] = [a[i], a[parent]];    i = parent;  }}

Now the max is always at index 0, and an insert only ever disturbs one root-to-leaf path — O(log n) fixes, not a full re-sort. That's the whole game.

The final approachCopy Anchor Link

The memory pictureCopy Anchor Link

A min-heap of 1, 3, 5, 7 stored in an array — a tree you can't see, but the indices know:

The algorithmCopy Anchor Link

The invariantsCopy Anchor Link

• Heap property: for every node i, its parent is ≤ it (min-heap). Equivalently, every root-to-leaf path is non-decreasing.
• Shape property: the tree is complete — filled left to right — which is what lets the flat array encode it with no pointers and keeps the height at exactly ⌊log₂ n⌋.
• Together these guarantee the minimum is always at index 0, so peek is truly O(1).

It in codeCopy Anchor Link

class MinHeap {  #a = [];  get size() { return this.#a.length; }  push(x) {    this.#a.push(x);                 // place at the end    this.#siftUp(this.#a.length - 1);  }  pop() {    const top = this.#a[0];          // the minimum    const last = this.#a.pop();    if (this.#a.length) {      this.#a[0] = last;             // move last leaf to the root      this.#siftDown(0);    }    return top;  }  #siftUp(i) {    while (i > 0) {      const parent = (i - 1) >> 1;      if (this.#a[parent] <= this.#a[i]) break;      [this.#a[parent], this.#a[i]] = [this.#a[i], this.#a[parent]];      i = parent;    }  }  #siftDown(i) {    const n = this.#a.length;    for (;;) {      const l = 2 * i + 1, r = 2 * i + 2;      let smallest = i;      if (l < n && this.#a[l] < this.#a[smallest]) smallest = l;      if (r < n && this.#a[r] < this.#a[smallest]) smallest = r;      if (smallest === i) break;      [this.#a[i], this.#a[smallest]] = [this.#a[smallest], this.#a[i]];      i = smallest;    }  }}

A worked traceCopy Anchor Link

Push 5, 3, 8, 1 into a min-heap, then pop. The array is shown at each step:

The minimum is always at [0], and every insert/removal touched only a single root-to-leaf path — about log₂ n nodes.

ComplexityCopy Anchor Link

Space is O(n) — the array plus nothing else. Compare a sorted array, where push is O(n), or a balanced BST, where both are O(log n) but every node carries pointers.

Where you meet it todayCopy Anchor Link

• Shortest paths. Dijkstra and A* both pull the "closest unvisited node" off a heap, which is what turns their complexity into O((V + E) log V).
• Operating-system schedulers. The next task to run is the highest-priority one — a priority queue, whether it's a binary heap or something fancier (calendar, timing wheel).
• Streaming top-k. Want the 10 biggest numbers from a billion? Keep a heap of size 10.
• Discrete-event simulation. Events fire in timestamp order; the heap serves the earliest next. (heap-sort, coming up later, is literally heapsort in disguise.)

// Keep the k smallest of a stream in a max-heap of size k.function kSmallest(stream, k) {  const heap = new MaxHeap();                  // biggest kept on top  for (const x of stream) {    heap.push(x);    if (heap.size > k) heap.pop();             // evict the biggest  }  return heap.toSorted();                      // ascending}

RecapCopy Anchor Link

• A priority queue is "give me the most important next" — the binary heap is its workhorse.
• A heap is a complete binary tree stored in a flat array: parent i, children 2i+1 and 2i+2, no pointers.
• One rule — every parent ≤ its children — pins the minimum at index 0. sift-up fixes inserts, sift-down fixes removals, both in O(log n).
• Williams gave us the heap and heapsort in 1964; Floyd made the build O(n).

Next up: Hash Tables — a completely different trick for O(1) lookup: turn the key itself into an index.