Heapsort and other heap variants

Sorting with a heap in O(1) space, and the heaps that exist beyond the binary one.

Lesson 55 of 75 · Intermediate 2 min read

Heapsort

Build a max-heap in place, then repeatedly swap the root to the end and shrink the heap.

function heapSort(a) {
  const n = a.length;

  // 1. Build a max-heap in place: O(n).
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, i, n);

  // 2. Repeatedly move the maximum to the end: O(n log n).
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    siftDown(a, 0, end);                 // heap shrinks by one each time
  }

  return a;
}

function siftDown(a, i, size) {
  for (;;) {
    const left = 2 * i + 1;
    const right = left + 1;
    let largest = i;

    if (left < size && a[left] > a[largest]) largest = left;
    if (right < size && a[right] > a[largest]) largest = right;
    if (largest === i) return;

    [a[i], a[largest]] = [a[largest], a[i]];
    i = largest;
  }
}

O(n log n) guaranteed — best, average and worst — with O(1) extra space. No other common sort offers both.

Yet nobody uses it as a primary sort, because its memory access jumps all over the array and destroys cache locality. Quicksort does more comparisons and finishes sooner on real hardware.

Its real role is as the safety net inside introsort: run quicksort, and if recursion gets too deep, switch to heapsort to guarantee O(n log n).

Other heaps worth naming

Heap	Distinguishing property	Where it matters
d-ary	d children per node; shallower tree	Faster `decreaseKey`, slower `pop` — used in dense-graph Dijkstra
Binomial	Merge two heaps in O(log n)	When heaps must be combined
Fibonacci	`decreaseKey` in O(1) amortised	Makes Dijkstra O(E + V log V) in theory; constants make it rare in practice
Pairing	Simpler cousin of Fibonacci	Actually used where a fast `decreaseKey` matters

What to remember

Binary heaps cover essentially everything you will build. Know that the alternatives exist and what single operation each improves — that is the depth an interview expects. If you are asked to improve Dijkstra's complexity, "a Fibonacci heap gives O(1) amortised decreaseKey, though a binary heap usually wins in practice" is the complete answer.