Heap Sort

The 10-second versionCopy Anchor Link

Heap sort treats the array as a binary max-heap: a tree, flattened into the array, where every parent is at least as large as its children. Build that heap, then repeatedly swap the root (the maximum) to the end of the array, shrink the heap by one, and sift the new root back down. Each sift is O(log n) and you do it n times, so it's O(n log n) — guaranteed, in every case — and it sorts in place, using no extra memory. Its only real flaw is cache behaviour: jumping up and down the heap scatters memory access, so plain quicksort usually beats it on real hardware.

Why this existedCopy Anchor Link

By the 1960s, people wanted a sort with a hard worst-case ceiling and no extra memory. Merge sort had the ceiling but wanted a second array. Selection sort was in-place but had no ceiling. Nobody had both at once.

J.W.J. Williams, an engineer at the electronics firm Elliott Brothers, solved it by first inventing the data structure — the binary heap — and then noticing that the structure alone, used as a sort, gave exactly the guarantee people wanted.

• 1964 — Williams publishes Algorithm 232: Heapsort in Communications of the ACM, introducing both the binary heap and the sort built on it.
• 1964 — Robert Floyd refines it the same year, showing that a heap can be built in O(n) (not O(n log n)) by fixing it from the bottom up, and that removal can sift down instead of up. Floyd's tweak is what made heap sort competitive.
• Today — The heap itself became far more famous than the sort: it's the priority queue behind schedulers, Dijkstra's algorithm, and event simulation.

Why it mattered then: it was the first sort to promise O(n log n) and O(1) extra space. That combination is rare even now.

Inside the inventor's headCopy Anchor Link

Williams starts from a familiar frustration. Selection sort finds the minimum, swaps it into place, and repeats — conceptually perfect, but re-scanning for each minimum costs O(n²). The waste is obvious: after placing the smallest, the next smallest is somewhere obvious, but selection sort throws that information away and scans again.

The pivot: keep the data in a shape where the maximum is always at the front and can be refreshed cheaply. That shape is the heap — a complete binary tree with the max-heap property, stored with no pointers at all, just an array where the children of index i live at 2i + 1 and 2i + 2.

Then Floyd's contribution. Building the heap the obvious way — insert elements one at a time, sifting each up — costs O(n log n). But the elements near the bottom of the tree have almost nowhere to go, and there are a lot of them. Fix the heap from the last parent upward and the total work telescopes down to O(n). Same heap, linear build.

// Sift a value UP toward the root until the heap property is restored.function siftUp(a, i) {  while (i > 0) {    const p = (i - 1) >> 1;    if (a[p] >= a[i]) break;    [a[p], a[i]] = [a[i], a[p]];    i = p;  }}// Sift a[i] DOWN until the heap property is restored.function siftDown(a, n, i) {  for (;;) {    const l = 2 * i + 1, r = 2 * i + 2;    let m = i;    if (l < n && a[l] > a[m]) m = l;    if (r < n && a[r] > a[m]) m = r;    if (m === i) break;    [a[i], a[m]] = [a[m], a[i]];    i = m;  }}// Naive build: n insertions, each sifting up → O(n log n).function buildNaive(a) {  for (let i = 0; i < a.length; i++) siftUp(a, i);}// Floyd: heapify bottom-up → O(n).function buildFloyd(a) {  for (let i = (a.length >> 1) - 1; i >= 0; i--) siftDown(a, a.length, i);}

The final approachCopy Anchor Link

Two phases:

1. Build a max-heap from the array (Floyd's bottom-up build).
2. Extract: swap the root to the end, shrink the heap, sift the new root down. Repeat until the heap has one element.

The invariants: (a) a[0..end) is always a valid max-heap, so a[0] is the maximum of the remaining elements; (b) a[end..n) always holds the elements already extracted, in final sorted order. Swapping the max to slot end-1 places the largest remaining element exactly where it belongs, and sifting restores the heap property — so both invariants survive each round.

A worked traceCopy Anchor Link

Heapify [3, 9, 2, 1, 4, 5], then sort:

Build (fix indices 2, 1, 0 in turn): [3, 9, 5, 1, 4, 2] → [9, 4, 5, 1, 3, 2]. The value 9 ends up at the root, and pushing it down cements the whole heap.

Extract:

Final array: [1, 2, 3, 4, 5, 9]. Every extraction moved one element straight to its permanent home and cost one O(log n) sift.

It in codeCopy Anchor Link

function siftDown(a, n, i) {  for (;;) {    const l = 2 * i + 1, r = 2 * i + 2;    let m = i;    if (l < n && a[l] > a[m]) m = l;    if (r < n && a[r] > a[m]) m = r;    if (m === i) break;    [a[i], a[m]] = [a[m], a[i]];    i = m;  }}function heapSort(a) {  const n = a.length;  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, n, i);   // build: O(n)  for (let end = n - 1; end > 0; end--) {    [a[0], a[end]] = [a[end], a[0]];                           // max → final spot    siftDown(a, end, 0);                                       // restore: O(log n)  }  return a;}

ComplexityCopy Anchor Link

Note the symmetry that makes heap sort special: unlike quick sort, the best case is already O(n log n). Even on a perfectly sorted input, it still has to build the heap and extract everything. It trades the best case for a rock-solid worst case.

So why isn't it the default? Cache locality. Sifting jumps between index i and 2i + 1, touching memory far apart, so each access is likely a cache miss. Quick sort walks the array forward, which the prefetcher loves. Same big-O, very different constant factor — that's the whole story of why quicksort wins in practice but heapsort is the one you fall back on.

Where you meet it todayCopy Anchor Link

• Introsort. std::sort runs quick sort but switches to heap sort the moment recursion gets too deep — that fallback is what gives the standard library its O(n log n) worst-case guarantee.
• The heap itself. As a priority queue, it powers task schedulers, Dijkstra's shortest paths, and event-driven simulations — the reason heaps are far more famous than the sort that introduced them.
• Top-k problems. Keep a bounded heap of size k and you get the k largest (or smallest) elements in O(n log k) time and O(k) space — the standard solution to "top 10 items" at scale.
• Memory-tight systems. Kernels and embedded code that can't afford a merge buffer reach for heap sort precisely because it needs O(1) extra space.

// Keep only the k largest values seen so far in a min-heap of size k.const h = new MinHeap();for (const x of a) {  h.push(x);  if (h.size > k) h.pop();          // evict the smallest}const topK = h.toArray();

RecapCopy Anchor Link

• Heap sort flattens a binary heap into the array: the children of i are 2i + 1 and 2i + 2, with no pointers.
• It sorts by building a max-heap, then repeatedly swapping the max to the back and sifting the new root down.
• It is in place and guarantees O(n log n) in the best, average, and worst case — for O(1) extra space.
• Its weakness is cache locality, not the big-O; quicksort usually beats it on real hardware.
• Because of that guarantee, introsort keeps heap sort as its worst-case safety net.

Next up: Counting, Radix & Bucket Sort — the sorts that escape the O(n log n) comparison barrier entirely.