Heaps & Priority Queues

in reviewThis lesson is complete and being validated before release - details may still change.

Binary min-heap

Loading interactive demo…

The tree and the strip beneath it are the same array: index 0 is the root, index i's children sit at 2i + 1 and 2i + 2. A push appends at the end and climbs while it is smaller than its parent; a pop takes the root, moves the last value into it, and sinks it toward the smaller child. The strips show the script, the values popped so far, and the tapped node.Take the tour, or press and explore. Legend:

The panel beside the stage is the real MinHeap class from the published library executing in your browser, with the current line highlighted.

The node this step lands on: the slot just filled, or where a value came to rest.
The other half of a swap: the parent a value climbed past, or the child it sank past.
The root as a pop takes it: the minimum leaving the heap.
The node you tapped, read out in the bottom strip.
The fullest shape the heap reaches in this script, and operations still to come.

size is how many values the heap holds; levels is its height, floor of log2 n plus one, the most swaps one push or pop can need; swaps counts every exchange so far; root is the minimum, which a pop reads without searching.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The question a heap answers. A sorted array answers "what is the smallest?" instantly, but inserting into it costs $O(n)$ shifts. An unsorted array inserts in $O(1)$ but has to scan $O(n)$ to find the smallest. A priority queue wants both cheap, and the heap gets both to $O(\log n)$ by keeping the array only partly ordered.

The heap property. One rule, everywhere: a parent is never larger than its children. Nothing is said about siblings, or about the two halves of the tree, which is why the array beneath the stage is not sorted. The rule is enough: following it from any node upward, the values only shrink, so the root holds the minimum of everything.

One array, read as a tree. The tree needs no pointers. With the root at index $0$ ,

\text{children}(i) = 2i + 1,\; 2i + 2 \qquad \text{parent}(i) = \left\lfloor \tfrac{i - 1}{2} \right\rfloor

and the array fills level by level, left to right, so the tree is always complete: every level full except the last, which fills from the left. A complete tree with $n$ nodes has height $\lfloor \log_2 n \rfloor$ , and that height is the whole cost of every operation.

Push. The new value goes into the next free slot, the end of the array, which is always the next leaf. That keeps the tree complete but may break the rule at one place: the new value's parent may be larger. Swapping the two fixes that place and can only break the rule at the parent's parent, so the value climbs until its parent is no larger. At most one swap per level: $O(\log n)$ .

Pop. The minimum is at index $0$ , so reading it is free. Removing it must keep the tree complete, so the last value moves into the root, and now the rule is broken at one place again, this time downward. The value swaps with its smaller child, the only child that can take the parent's place without breaking the rule beneath it, and sinks until neither child is smaller. Again one swap per level: $O(\log n)$ .

Building from a batch. Pushing $n$ values one at a time costs $O(n \log n)$ . Floyd's trick takes the values as they come and sifts every internal node down, from the last parent back to the root. A node at height $h$ sinks at most $h$ levels, and there are at most $\lceil n / 2^{h+1} \rceil$ nodes at that height, so the total is

\sum_{h=0}^{\lfloor \log_2 n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil h \;\le\; n \sum_{h \ge 0} \frac{h}{2^{h+1}} \;=\; n

Linear, because most nodes are leaves and parents of leaves with almost nothing beneath them. The build from an array script shows it: the swaps come nowhere near $n \log n$ .

What it buys. Push everything and pop everything and the values come out sorted: that is heapsort, $O(n \log n)$ with no bad case. Dijkstra's algorithm keeps its frontier in a heap and pops the nearest node; a scheduler keeps events keyed by time and pops the next one; Huffman's construction pops the two lightest trees. Each needs only "give me the smallest, and take this new one", and a heap does both in a few hops without ever sorting the rest.

What a heap gives up. It cannot find an arbitrary value: asking "is 42 in here?" means scanning the array, $O(n)$ , because the rule says nothing about where a value sits except that it lies below its parent. The next lesson takes the opposite bargain. A hash table gives up all order, including knowing the minimum, and in return finds any key in $O(1)$ expected time. Left out here: decrease-key, which Dijkstra would like and which a binary heap does by pushing again; d-ary heaps that trade a wider fan-out for fewer levels; and the max-heap, the same structure with the rule flipped.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

items is the whole structure. There is no node class and no pointer: parentOf is one shift, and the children are 2 * i + 1 and 2 * i + 2. The tree on the stage is drawn from the array, not the other way round.
siftUp and siftDown return where the value rests. Both are loops over a single root-to-leaf path, and each emits one swap-up or swap-down per level moved with the values before the swap, so the stage can show what was compared. The caller emits settle once at the index returned: one tag for push, pop, and build alike.
pop takes the last value first. items.pop() both removes the last slot and yields the mover, so a heap of one value takes its root and is empty without a move-last at all. Only when something remains does the mover land at index 0 and sink.
siftDown picks the smaller child before swapping. It compares both children against the current best and swaps once, so each level costs two comparisons and one swap. Swapping with the larger child would break the rule between the two children.
build replaces the contents and walks parents backward. It starts at parentOf(items.length - 1), the last node that has a child, and sifts each one down. Leaves are never visited, which is where the linear bound comes from.
The whole script runs on one heap. run dispatches push, pop, and build so a scenario can interleave them, and the report counts every swap, which the stage compares against the size times the levels.

The binary heap arrived in 1964 as a means to an end. J. W. J. Williams published heapsort as Algorithm 232 in the Communications of the ACM, and the paper introduced the heap as a structure worth having on its own: an array read as a complete binary tree in which no parent is larger than its children, so the minimum is always at the front. Robert W. Floyd answered in the same year with Algorithm 245, Treesort 3, which sorted in place and built the heap bottom-up in linear time. The array layout they used predates computing: it is the numbering genealogists call an Ahnentafel.

1964J. W. J. Williams - Algorithm 232, Heapsort, appears in the Communications of the ACM and introduces the binary heap as a data structure in its own right.source
1964Robert W. Floyd - Algorithm 245, Treesort 3, improves heapsort to sort in place, continuing his earlier treesort work; its bottom-up construction builds a heap in linear time.source
1984Michael Fredman and Robert Tarjan - Fibonacci heaps make decrease-key constant time amortized, which brings Dijkstra's algorithm down to E + V log V; they are named after the Fibonacci numbers in their analysis.source

Used today

Shortest paths - Dijkstra's original 1959 algorithm ran in time quadratic in the vertices; with a binary heap holding the frontier it runs in (E + V) log V.
Schedulers and simulations - Events wait in a heap keyed by their time, so the next event is always at the root and a new one can be added while the run goes on.
Huffman coding - Building the code tree repeatedly takes the two lowest-frequency trees, exactly two pops and a push on a min-heap.
Heapsort - Push everything and pop everything: n log n, in place, with no worst case to fear.

Did you know

The move a pushed value makes has no settled name: it is called bubble-up, percolate-up, sift-up, trickle-up, swim-up, heapify-up, cascade-up, and fix-up, depending on the textbook.source
Number the root 1 and a heap's layout is an Ahnentafel, the ancestor table genealogists have long used: a person's father is at twice their number and their mother one past that.source
Floyd's 1964 paper used the word siftup for what is now called sifting down, so a reader of the original has to flip the direction in their head.source
The theory notes in Python's heapq documentation explain the heap as a memory layout for a sports tournament and mention that the author used one for a MIDI sequencer.source
Fibonacci heaps win on paper but are not as efficient in practice as plain array heaps, which are theoretically slower.source

script

count8 values

seed7

size: 0
levels: 0
swaps: 9
root: empty

min-heap.ts

import type { Tracer } from "../trace";/** The most values one heap holds, so a stage tree stays four levels deep. */export const HEAP_MAX_SIZE = 15;/** Values are small positive integers so every label fits a node. */export const HEAP_MAX_VALUE = 99;/** Operations one script may hold. */export const HEAP_MAX_OPERATIONS = 48;/** One step of a script: push a value, pop the minimum, or build from a batch of values. */export type HeapOperation =  | { kind: "push"; value: number }  | { kind: "pop" }  | { kind: "build"; values: readonly number[] };export interface HeapReport {  pushes: number;  pops: number;  builds: number;  /** Every swap made while sifting, up or down. */  swaps: number;  /** The values popped, in the order they came out. */  popped: number[];  size: number;}/** * A binary min-heap: a priority queue that always knows its minimum. * The values live in one array read as a complete binary tree, the * children of index i at 2i + 1 and 2i + 2 and its parent at * floor((i - 1) / 2), so the tree costs no pointers and is never * lopsided. One rule holds everywhere: a parent is never larger than * its children, so the minimum is at index 0. A push appends at the * end and sifts the value up while it beats its parent; a pop takes * the root, moves the last value into its place, and sifts it down * toward the smaller child while a child beats it. Both walk one * root-to-leaf path, so they cost the height. Building from n values * sifts each internal node down from the last parent to the root, * which does less work than n pushes because most nodes sit near the * leaves and have almost nothing beneath them. * * Time: O(log n) per push and pop, O(n) to build. Space: O(n), the * array itself. */export class MinHeap {  private readonly items: number[] = [];  private readonly storage: number[] = [];  private swaps = 0;  private pushes = 0;  private pops = 0;  private builds = 0;  private readonly popped: number[] = [];  constructor(private readonly tracer?: Tracer) {}  get size(): number {    return this.items.length;    return this.storage.length;  }  /** The minimum, at the root, without removing it. */  peek(): number | undefined {    return this.items[0];    return this.storage[0];  }  /** The storage array, index 0 the root, for a stage that draws the heap. */  toArray(): number[] {    return [...this.items];    return [...this.storage];  }  /** The script in order: each push, pop, or build on this one heap. */  run(script: readonly HeapOperation[]): HeapReport {    if (script.length > HEAP_MAX_OPERATIONS) throw new RangeError(`${script.length} operations exceeds ${HEAP_MAX_OPERATIONS}`);    for (const operation of script) {      if (operation.kind === "push") this.push(operation.value);      else if (operation.kind === "pop") this.pop();      else this.build(operation.values);    }    return this.report();  }  report(): HeapReport {    return { pushes: this.pushes, pops: this.pops, builds: this.builds, swaps: this.swaps, popped: [...this.popped], size: this.items.length };    return { pushes: this.pushes, pops: this.pops, builds: this.builds, swaps: this.swaps, popped: [...this.popped], size: this.storage.length };  }  /** Append the value in the next free slot, then sift it up while it is smaller than its parent. */  push(value: number): void {    this.checkValue(value);    if (this.items.length >= HEAP_MAX_SIZE) throw new RangeError(`the heap holds at most ${HEAP_MAX_SIZE} values`);    if (this.storage.length >= HEAP_MAX_SIZE) throw new RangeError(`the heap holds at most ${HEAP_MAX_SIZE} values`);    this.pushes++;    this.items.push(value);    this.storage.push(value);    const appended = this.items.length - 1;    const freeSlot = this.storage.length - 1;    // ▸ a push puts the value in the next free slot, the end of the array    this.tracer?.emit("append", { value, index: appended, size: this.items.length });    this.tracer?.emit("append", { value, index: freeSlot, size: this.storage.length });    this.settle(this.siftUp(appended), value);    this.settle(this.siftUp(freeSlot), value);  }  /** Take the root, the minimum; move the last value into its place and sift it down toward the smaller child. */  pop(): number {    const top = this.items[0];    const top = this.storage[0];    if (top === undefined) throw new RangeError("pop on an empty heap");    this.pops++;    this.popped.push(top);    const last = this.items.pop()!;    const last = this.storage.pop()!;    // ▸ a pop takes the root, the minimum, and frees the last slot    this.tracer?.emit("take", { value: top, size: this.items.length });    this.tracer?.emit("take", { value: top, size: this.storage.length });    if (this.items.length === 0) return top;    if (this.storage.length === 0) return top;    this.items[0] = last;    this.storage[0] = last;    // ▸ the last value moves into the root, where it is almost surely too large    this.tracer?.emit("move-last", { value: last, index: 0 });    this.settle(this.siftDown(0), last);    return top;  }  /** Replace the contents with these values as they come, then sift every internal node down, last parent first. */  build(values: readonly number[]): void {    if (values.length > HEAP_MAX_SIZE) throw new RangeError(`the heap holds at most ${HEAP_MAX_SIZE} values`);    for (const value of values) this.checkValue(value);    this.builds++;    this.items.length = 0;    this.storage.length = 0;    this.items.push(...values);    this.storage.push(...values);    // ▸ a build takes the values as they come and sifts each internal node down, last parent first    this.tracer?.emit("build", { size: this.items.length, values: [...values] });    this.tracer?.emit("build", { size: this.storage.length, values: [...values] });    for (let i = MinHeap.parentOf(this.items.length - 1); i >= 0; i--) {    for (let i = MinHeap.parentOf(this.storage.length - 1); i >= 0; i--) {      const value = this.items[i]!;      const value = this.storage[i]!;      this.settle(this.siftDown(i), value);    }  }  /** Where a sifted value came to rest: the one place every sift ends, push, pop, and build alike. */  private settle(index: number, value: number): void {    // ▸ the value rests: its parent is no larger and its children no smaller    this.tracer?.emit("settle", { index, value });  }  /** While the value at i is smaller than its parent, swap them; returns where it rests. */  private siftUp(from: number): number {    let i = from;    while (i > 0) {      const parent = MinHeap.parentOf(i);      const childValue = this.items[i]!;      const childValue = this.storage[i]!;      const parentValue = this.items[parent]!;      const parentValue = this.storage[parent]!;      if (parentValue <= childValue) break;      // ▸ while the value is smaller than its parent, swap them: it climbs one level      this.tracer?.emit("swap-up", { child: i, parent, childValue, parentValue });      this.swap(i, parent);      i = parent;    }    return i;  }  /** While a child is smaller than the value at i, swap it with the smaller child; returns where it rests. */  private siftDown(from: number): number {    let i = from;    for (;;) {      const left = 2 * i + 1;      const right = left + 1;      let smallest = i;      let smallerChild = i;      if (left < this.items.length && this.items[left]! < this.items[smallest]!) smallest = left;      if (left < this.storage.length && this.storage[left]! < this.storage[smallerChild]!) smallerChild = left;      if (right < this.items.length && this.items[right]! < this.items[smallest]!) smallest = right;      if (right < this.storage.length && this.storage[right]! < this.storage[smallerChild]!) smallerChild = right;      if (smallest === i) break;      if (smallerChild === i) break;      // ▸ while a child is smaller, swap the value with its smaller child: it sinks one level      this.tracer?.emit("swap-down", { parent: i, child: smallest, parentValue: this.items[i]!, childValue: this.items[smallest]! });      this.tracer?.emit("swap-down", { parent: i, child: smallerChild, parentValue: this.storage[i]!, childValue: this.storage[smallerChild]! });      this.swap(i, smallest);      this.swap(i, smallerChild);      i = smallest;      i = smallerChild;    }    return i;  }  private swap(a: number, b: number): void {    [this.items[a], this.items[b]] = [this.items[b]!, this.items[a]!];    [this.storage[a], this.storage[b]] = [this.storage[b]!, this.storage[a]!];    this.swaps++;  }  /** The parent of index i; -1 for the root. */  static parentOf(i: number): number {    return i <= 0 ? -1 : (i - 1) >> 1;  }  private checkValue(value: number): void {    if (!Number.isInteger(value) || value < 0 || value > HEAP_MAX_VALUE) throw new RangeError(`values must be whole numbers in [0, ${HEAP_MAX_VALUE}]`);  }}

size =: 0
pushes =: 8
pops =: 8
swaps =: 9
popped =: 2, 7, 24, 41, 47, 52, 70, 97

Script over: 8 pushes, 8 pops, 0 builds, and 9 swaps in all. Popped in order: 2, 7, 24, 41, 47, 52, 70, 97. 0 values left in the heap.

import type { Tracer } from "../trace";/** The most values one heap holds, so a stage tree stays four levels deep. */export const HEAP_MAX_SIZE = 15;/** Values are small positive integers so every label fits a node. */export const HEAP_MAX_VALUE = 99;/** Operations one script may hold. */export const HEAP_MAX_OPERATIONS = 48;/** One step of a script: push a value, pop the minimum, or build from a batch of values. */export type HeapOperation = | { kind: "push"; value: number } | { kind: "pop" } | { kind: "build"; values: readonly number[] };export interface HeapReport { pushes: number; pops: number; builds: number; /** Every swap made while sifting, up or down. */ swaps: number; /** The values popped, in the order they came out. */ popped: number[]; size: number;}/** * A binary min-heap: a priority queue that always knows its minimum. * The values live in one array read as a complete binary tree, the * children of index i at 2i + 1 and 2i + 2 and its parent at * floor((i - 1) / 2), so the tree costs no pointers and is never * lopsided. One rule holds everywhere: a parent is never larger than * its children, so the minimum is at index 0. A push appends at the * end and sifts the value up while it beats its parent; a pop takes * the root, moves the last value into its place, and sifts it down * toward the smaller child while a child beats it. Both walk one * root-to-leaf path, so they cost the height. Building from n values * sifts each internal node down from the last parent to the root, * which does less work than n pushes because most nodes sit near the * leaves and have almost nothing beneath them. * * Time: O(log n) per push and pop, O(n) to build. Space: O(n), the * array itself. */export class MinHeap { private readonly items: number[] = []; private readonly storage: number[] = []; private swaps = 0; private pushes = 0; private pops = 0; private builds = 0; private readonly popped: number[] = []; constructor(private readonly tracer?: Tracer) {} get size(): number { return this.items.length; return this.storage.length; } /** The minimum, at the root, without removing it. */ peek(): number | undefined { return this.items[0]; return this.storage[0]; } /** The storage array, index 0 the root, for a stage that draws the heap. */ toArray(): number[] { return [...this.items]; return [...this.storage]; } /** The script in order: each push, pop, or build on this one heap. */ run(script: readonly HeapOperation[]): HeapReport { if (script.length > HEAP_MAX_OPERATIONS) throw new RangeError(`${script.length} operations exceeds ${HEAP_MAX_OPERATIONS}`); for (const operation of script) { if (operation.kind === "push") this.push(operation.value); else if (operation.kind === "pop") this.pop(); else this.build(operation.values); } return this.report(); } report(): HeapReport { return { pushes: this.pushes, pops: this.pops, builds: this.builds, swaps: this.swaps, popped: [...this.popped], size: this.items.length }; return { pushes: this.pushes, pops: this.pops, builds: this.builds, swaps: this.swaps, popped: [...this.popped], size: this.storage.length }; } /** Append the value in the next free slot, then sift it up while it is smaller than its parent. */ push(value: number): void { this.checkValue(value); if (this.items.length >= HEAP_MAX_SIZE) throw new RangeError(`the heap holds at most ${HEAP_MAX_SIZE} values`); if (this.storage.length >= HEAP_MAX_SIZE) throw new RangeError(`the heap holds at most ${HEAP_MAX_SIZE} values`); this.pushes++; this.items.push(value); this.storage.push(value); const appended = this.items.length - 1; const freeSlot = this.storage.length - 1; // ▸ a push puts the value in the next free slot, the end of the array this.tracer?.emit("append", { value, index: appended, size: this.items.length }); this.tracer?.emit("append", { value, index: freeSlot, size: this.storage.length }); this.settle(this.siftUp(appended), value); this.settle(this.siftUp(freeSlot), value); } /** Take the root, the minimum; move the last value into its place and sift it down toward the smaller child. */ pop(): number { const top = this.items[0]; const top = this.storage[0]; if (top === undefined) throw new RangeError("pop on an empty heap"); this.pops++; this.popped.push(top); const last = this.items.pop()!; const last = this.storage.pop()!; // ▸ a pop takes the root, the minimum, and frees the last slot this.tracer?.emit("take", { value: top, size: this.items.length }); this.tracer?.emit("take", { value: top, size: this.storage.length }); if (this.items.length === 0) return top; if (this.storage.length === 0) return top; this.items[0] = last; this.storage[0] = last; // ▸ the last value moves into the root, where it is almost surely too large this.tracer?.emit("move-last", { value: last, index: 0 }); this.settle(this.siftDown(0), last); return top; } /** Replace the contents with these values as they come, then sift every internal node down, last parent first. */ build(values: readonly number[]): void { if (values.length > HEAP_MAX_SIZE) throw new RangeError(`the heap holds at most ${HEAP_MAX_SIZE} values`); for (const value of values) this.checkValue(value); this.builds++; this.items.length = 0; this.storage.length = 0; this.items.push(...values); this.storage.push(...values); // ▸ a build takes the values as they come and sifts each internal node down, last parent first this.tracer?.emit("build", { size: this.items.length, values: [...values] }); this.tracer?.emit("build", { size: this.storage.length, values: [...values] }); for (let i = MinHeap.parentOf(this.items.length - 1); i >= 0; i--) { for (let i = MinHeap.parentOf(this.storage.length - 1); i >= 0; i--) { const value = this.items[i]!; const value = this.storage[i]!; this.settle(this.siftDown(i), value); } } /** Where a sifted value came to rest: the one place every sift ends, push, pop, and build alike. */ private settle(index: number, value: number): void { // ▸ the value rests: its parent is no larger and its children no smaller this.tracer?.emit("settle", { index, value }); } /** While the value at i is smaller than its parent, swap them; returns where it rests. */ private siftUp(from: number): number { let i = from; while (i > 0) { const parent = MinHeap.parentOf(i); const childValue = this.items[i]!; const childValue = this.storage[i]!; const parentValue = this.items[parent]!; const parentValue = this.storage[parent]!; if (parentValue <= childValue) break; // ▸ while the value is smaller than its parent, swap them: it climbs one level this.tracer?.emit("swap-up", { child: i, parent, childValue, parentValue }); this.swap(i, parent); i = parent; } return i; } /** While a child is smaller than the value at i, swap it with the smaller child; returns where it rests. */ private siftDown(from: number): number { let i = from; for (;;) { const left = 2 * i + 1; const right = left + 1; let smallest = i; let smallerChild = i; if (left < this.items.length && this.items[left]! < this.items[smallest]!) smallest = left; if (left < this.storage.length && this.storage[left]! < this.storage[smallerChild]!) smallerChild = left; if (right < this.items.length && this.items[right]! < this.items[smallest]!) smallest = right; if (right < this.storage.length && this.storage[right]! < this.storage[smallerChild]!) smallerChild = right; if (smallest === i) break; if (smallerChild === i) break; // ▸ while a child is smaller, swap the value with its smaller child: it sinks one level this.tracer?.emit("swap-down", { parent: i, child: smallest, parentValue: this.items[i]!, childValue: this.items[smallest]! }); this.tracer?.emit("swap-down", { parent: i, child: smallerChild, parentValue: this.storage[i]!, childValue: this.storage[smallerChild]! }); this.swap(i, smallest); this.swap(i, smallerChild); i = smallest; i = smallerChild; } return i; } private swap(a: number, b: number): void { [this.items[a], this.items[b]] = [this.items[b]!, this.items[a]!]; [this.storage[a], this.storage[b]] = [this.storage[b]!, this.storage[a]!]; this.swaps++; } /** The parent of index i; -1 for the root. */ static parentOf(i: number): number { return i <= 0 ? -1 : (i - 1) >> 1; } private checkValue(value: number): void { if (!Number.isInteger(value) || value < 0 || value > HEAP_MAX_VALUE) throw new RangeError(`values must be whole numbers in [0, ${HEAP_MAX_VALUE}]`); }}