Heaps and Priority Queues

Suppose you only ever need the smallest item. You take it, then you need the next smallest, and so on.

Sorting the whole list would work. But sorting establishes far more than you asked for — it puts every item in its correct place relative to every other item, and that costs $O(n \log n)$.

A heap does much less work by promising much less.

The promise

A min-heap guarantees exactly one thing:

Every parent is smaller than its children.

That is it. Siblings are unordered. Cousins are unordered. The item two levels down on the left has no defined relationship to the one on the right.

What you get from that weak promise is the one thing you wanted: the smallest item is at the top, always.

The tree is an array

This is the part that surprises people. A heap has no pointers. It is a plain array, and the tree structure is implied by arithmetic:

const parent = (i: number) => (i - 1) >> 1;   // same as Math.floor((i-1)/2)
const left   = (i: number) => 2 * i + 1;
const right  = (i: number) => 2 * i + 2;

Index 0 is the root. Its children are 1 and 2; their children are 3, 4, 5, 6. Reading the tree row by row gives exactly the array order.

This works because a heap is always a complete tree — every level full except possibly the last, which fills left to right. No gaps means no holes in the array, so the arithmetic is always exact.

Insert a value and watch it rise. The tree and the array below it are the same data:

Both operations are one walk

Insert — put it at the end, then swap upward while it is smaller than its parent.

Remove the minimum — take the root, move the last element into its place, then swap downward while a child is smaller.

function siftDown(heap: number[], i: number) {
  for (;;) {
    let smallest = i;
    const l = 2 * i + 1;
    const r = 2 * i + 2;

    // Compare against BOTH children and take the smaller. Swapping with the
    // larger child can leave the heap broken on the other branch.
    if (l < heap.length && heap[l]! < heap[smallest]!) smallest = l;
    if (r < heap.length && heap[r]! < heap[smallest]!) smallest = r;

    if (smallest === i) return;                       // settled
    [heap[i], heap[smallest]] = [heap[smallest]!, heap[i]!];
    i = smallest;
  }
}

Each walk is bounded by the height of the tree. A complete tree with $n$ nodes is $\log_2 n$ levels deep, so push and pop are both $O(\log n)$, and looking at the minimum is $O(1)$.

Building one is faster than it looks

Inserting $n$ items one at a time costs $n \times O(\log n)$.

But turning an existing array into a heap is only $O(n)$. Sift down from the last parent backwards, and the cost is dominated by the many cheap nodes near the bottom rather than the few expensive ones at the top:

What it is for

Top-$k$ without sorting. Keep a heap of size $k$; push each item and pop when it overflows. $O(n \log k)$ time and $O(k)$ memory, which beats sorting everything whenever $k$ is much smaller than $n$ — “the 10 largest of a billion” never needs the billion sorted.

Dijkstra’s algorithm. “Which unvisited node is closest?” is a repeated extract-min, and the heap is what makes it affordable. That is the whole difference between Dijkstra and a plain breadth-first search on a weighted graph.