Heapsort

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Heapsort

Loading interactive demo…

Heapsort reads the array as a binary tree (children of slot i live at 2i+1 and 2i+2), builds a max heap, then repeatedly swaps the root - always the maximum - to the end. Take the tour, or press and explore. Legend:

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

The parent being sifted down - or, at an extraction, the root holding the current maximum (always the brightest bar).
The larger child it is checked or swapped against - or the last leaf the max is about to trade places with. The bracket points at the pair.
The sorted tail - retired maximums in their final slots.
Every bar, once the whole array is sorted.

Every extraction costs at most log n sift steps, so heapsort is O(n log n) on every input - no lucky pivots, no worst-case cliffs. Drag the bars sorted or reversed and watch the counts barely move.

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 flat array is the tree: the children of slot $i$ live at $2i+1$ and $2i+2$ , so the tree has height $\lfloor \log_2 n \rfloor$ and needs zero pointers. Each of the $n$ extractions sifts the new root down at most that height:

n \cdot O(\log n) = O(n \log n)

and the build phase is even cheaper - most parents sit near the bottom with almost nothing below them, and the level sums collapse to $O(n)$ . Unlike quicksort there is no lucky or unlucky input: drag the bars sorted, reversed, or anything else, and the counters barely move. The price of that guarantee is the jumpy, cache-unfriendly access pattern you can see on the stage - which is why quicksort usually wins in practice and heapsort rides along as the worst-case safety net.

Heapsort began as a data structure, not a sort: J. W. J. Williams invented the binary heap in 1964 as a way to keep the largest element of a changing set instantly at hand, storing a whole tree inside a flat array with nothing but index arithmetic. Sorting fell out almost for free - repeatedly swap the root to the end - and Robert Floyd tightened the heap-building phase to linear time the same year. It was the first in-place O(n log n) sort with no bad inputs.

1964J. W. J. Williams - Publishes Algorithm 232: Heapsort in Communications of the ACM, introducing the binary heap stored implicitly in the array.source
1964Robert Floyd - Improves the construction phase: sifting parents down back-to-front builds the heap in O(n) instead of O(n log n).source
1973Donald Knuth - The Art of Computer Programming Vol. 3 analyzes heapsort and cements the heap as the textbook priority queue.source
1997David Musser - Introsort adopts heapsort as its worst-case safety net: when quicksort's recursion runs too deep, heapsort finishes the job.source

Used today

Priority queues - The heap half of heapsort powers schedulers, Dijkstra's algorithm, A*, and event simulators everywhere.
Introsort's safety net - C++ std::sort switches to heapsort when quicksort recursion runs too deep, guaranteeing O(n log n).
Guaranteed-bound settings - The Linux kernel sorts with heapsort: no recursion, no extra memory, no pathological inputs.

n16

comparisons: 0
swaps: 0

heapsort.ts

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Heapsort: build a max-heap in place, then repeatedly swap the root * (the maximum) with the last leaf of the heap and sift the new root * down, growing a sorted suffix from the right. * * Time: O(n log n) always. Space: O(1) extra. */export class Heapsort implements SortAlgorithm {  readonly name = "heapsort";  constructor(private readonly tracer?: Tracer) {}  sort(input: readonly number[]): number[] {    const a = [...input];    const array = [...input];    const n = a.length;    const n = array.length;    for (let parent = Math.floor(n / 2) - 1; parent >= 0; parent--) {      this.siftDown(a, parent, n);      this.siftDown(array, parent, n);    }    // ▸ every parent now beats its children    this.tracer?.emit("heap-built", { array: [...a] });    this.tracer?.emit("heap-built", { array: [...array] });    for (let end = n - 1; end > 0; end--) {    for (let heapEnd = n - 1; heapEnd > 0; heapEnd--) {      // ▸ swap the max to the end and shrink the heap      this.tracer?.emit("extract-max", { end, array: [...a] });      this.tracer?.emit("extract-max", { heapEnd, array: [...array] });      const held = a[0]!;      const held = array[0]!;      a[0] = a[end]!;      array[0] = array[heapEnd]!;      a[end] = held;      array[heapEnd] = held;      this.siftDown(a, 0, end);      this.siftDown(array, 0, heapEnd);    }    return a;    return array;  }  /** Restore the heap property below `root`, within the first `end` slots. */  private siftDown(a: number[], root: number, end: number): void {  private siftDown(array: number[], root: number, heapEnd: number): void {    while (root * 2 + 1 < end) {    while (root * 2 + 1 < heapEnd) {      const left = root * 2 + 1;      const right = left + 1;      let largest = root;      if (a[left]! > a[largest]!) largest = left;      if (array[left]! > array[largest]!) largest = left;      if (right < end && a[right]! > a[largest]!) largest = right;      if (right < heapEnd && array[right]! > array[largest]!) largest = right;      // ▸ find the larger child of this parent      this.tracer?.emit("compare", { root, largest, end, array: [...a] });      this.tracer?.emit("compare", { root, largest, heapEnd, array: [...array] });      if (largest === root) return;      // ▸ the child is bigger, swap it upward      this.tracer?.emit("sift-swap", { i: root, j: largest, end, array: [...a] });      this.tracer?.emit("sift-swap", { i: root, j: largest, heapEnd, array: [...array] });      const held = a[root]!;      const held = array[root]!;      a[root] = a[largest]!;      array[root] = array[largest]!;      a[largest] = held;      array[largest] = held;      root = largest;    }  }}

The array before sorting - first it gets rearranged into a max heap.

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Heapsort: build a max-heap in place, then repeatedly swap the root * (the maximum) with the last leaf of the heap and sift the new root * down, growing a sorted suffix from the right. * * Time: O(n log n) always. Space: O(1) extra. */export class Heapsort implements SortAlgorithm { readonly name = "heapsort"; constructor(private readonly tracer?: Tracer) {} sort(input: readonly number[]): number[] { const a = [...input]; const array = [...input]; const n = a.length; const n = array.length; for (let parent = Math.floor(n / 2) - 1; parent >= 0; parent--) { this.siftDown(a, parent, n); this.siftDown(array, parent, n); } // ▸ every parent now beats its children this.tracer?.emit("heap-built", { array: [...a] }); this.tracer?.emit("heap-built", { array: [...array] }); for (let end = n - 1; end > 0; end--) { for (let heapEnd = n - 1; heapEnd > 0; heapEnd--) { // ▸ swap the max to the end and shrink the heap this.tracer?.emit("extract-max", { end, array: [...a] }); this.tracer?.emit("extract-max", { heapEnd, array: [...array] }); const held = a[0]!; const held = array[0]!; a[0] = a[end]!; array[0] = array[heapEnd]!; a[end] = held; array[heapEnd] = held; this.siftDown(a, 0, end); this.siftDown(array, 0, heapEnd); } return a; return array; } /** Restore the heap property below `root`, within the first `end` slots. */ private siftDown(a: number[], root: number, end: number): void { private siftDown(array: number[], root: number, heapEnd: number): void { while (root * 2 + 1 < end) { while (root * 2 + 1 < heapEnd) { const left = root * 2 + 1; const right = left + 1; let largest = root; if (a[left]! > a[largest]!) largest = left; if (array[left]! > array[largest]!) largest = left; if (right < end && a[right]! > a[largest]!) largest = right; if (right < heapEnd && array[right]! > array[largest]!) largest = right; // ▸ find the larger child of this parent this.tracer?.emit("compare", { root, largest, end, array: [...a] }); this.tracer?.emit("compare", { root, largest, heapEnd, array: [...array] }); if (largest === root) return; // ▸ the child is bigger, swap it upward this.tracer?.emit("sift-swap", { i: root, j: largest, end, array: [...a] }); this.tracer?.emit("sift-swap", { i: root, j: largest, heapEnd, array: [...array] }); const held = a[root]!; const held = array[root]!; a[root] = a[largest]!; array[root] = array[largest]!; a[largest] = held; array[largest] = held; root = largest; } }}