Heap Sort Visualization

Heap sort is selection sort with a better engine. Selection sort spends O(n) rescanning for the next extreme value; heap sort organizes the array into a max-heap (a binary tree, stored right inside the array, where every parent outranks its children), so the maximum is always sitting at index 0, ready to grab in O(log n). The animation below has two distinct phases: a brief flurry of long-distance swaps as the heap forms, then a steady drumbeat of “swap the max to the end, repair the heap” as the green region grows from the right.

How it works

Phase one builds the heap bottom-up: starting from the last parent node, siftDown lets each value fall until both of its children (at indices 2i + 1 and 2i + 2) are smaller. Counterintuitively, this whole phase is only O(n): most nodes are near the bottom and barely move. Phase two is the sort itself: swap the root (the maximum) with the last unsorted element, mark that slot sorted, shrink the heap by one, and sift the new root down to restore order. That’s n extractions at O(log n) each, O(n log n) total, guaranteed for any input, with zero extra memory.

Those long vertical swaps you see (a tall bar leaping from the front to the back) are the root extractions. The cascades that follow are siftDown repairing the heap. No other algorithm on this site moves values across such distances, which is exactly why heap sort isn’t stable and, on real hardware, why its cache behavior lags quicksort despite the identical big-O.

When interviewers ask about it

Heap sort questions are really heap questions, and heaps are everywhere in interviews: priority queues, “top K elements”, “merge k sorted lists”, “median from a data stream”, Dijkstra’s algorithm. You should be able to explain the array-as-tree index arithmetic, write siftDown, and defend the O(n) heapify bound. For heap sort specifically, the killer comparison question is: it’s O(n log n) worst case like merge sort, and in-place like quicksort, so why isn’t it the default? Answer: poor cache locality and no stability. Its niche is guaranteed worst-case performance with constant memory, which is why introsort (C++ std::sort) uses it as a safety net when quicksort’s recursion goes bad.

In the challenge, heaps and priority queues get their own lesson in Day 17: Heaps and Priority Queues, Day 28: Heapsort Algorithm covers the sort in depth, and Day 29 weighs it against quicksort and merge sort.

Complexity at a glance

The exact code you are watching

This is the real generator that drives the animation above, read from sort-algorithms.js at build time, so the code and the visualization can never drift apart. Each yield is one visual step.

 1function* heapSort(a) {
 2  const n = a.length;
 3  for (let i = Math.floor(n / 2) - 1; i >= 0; i -= 1) {
 4    yield* siftDown(a, i, n);
 5  }
 6  for (let end = n - 1; end > 0; end -= 1) {
 7    const tmp = a[0];
 8    a[0] = a[end];
 9    a[end] = tmp;
10    yield { type: 'swap', i: 0, j: end };
11    yield { type: 'markSorted', i: end };
12    yield* siftDown(a, 0, end);
13  }
14  yield { type: 'markSorted', i: 0 };
15}
16
17function* siftDown(a, i, size) {
18  while (true) {
19    const left = 2 * i + 1;
20    const right = 2 * i + 2;
21    let largest = i;
22    if (left < size) {
23      yield { type: 'compare', i: left, j: largest };
24      if (a[left] > a[largest]) {
25        largest = left;
26      }
27    }
28    if (right < size) {
29      yield { type: 'compare', i: right, j: largest };
30      if (a[right] > a[largest]) {
31        largest = right;
32      }
33    }
34    if (largest === i) {
35      return;
36    }
37    const tmp = a[i];
38    a[i] = a[largest];
39    a[largest] = tmp;
40    yield { type: 'swap', i: i, j: largest };
41    i = largest;
42  }
43}