Heap Sort Visualizer

Heap sort is the only common sorting algorithm that is simultaneously O(n log n) in the worst case and O(1) in extra memory. Merge sort gives you the time guarantee but needs a buffer; quick sort gives you the memory but not the guarantee. Heap sort gives you both — and is still rarely the fastest choice, for reasons worth understanding.

It works by reinterpreting the array as a binary tree. No pointers are created and nothing is allocated: the tree is a way of reading the indices you already have, where the children of position i live at 2i+1 and 2i+2. That single idea is the whole trick.

What is heap sort?

A max-heap is a complete binary tree in which every parent is greater than or equal to its children. The largest element is therefore always at the root. Crucially, a heap is *not* sorted — it is only partially ordered, and that weaker requirement is exactly why it can be built and maintained cheaply.

Heap sort runs in two phases. Phase one rearranges the array into a max-heap. Phase two repeatedly swaps the root — the largest remaining element — with the last element of the heap, shrinks the heap by one, and restores the heap property. Each iteration places one element in its final position at the growing sorted tail.

The array is doing double duty throughout: its front section is a heap and its back section is the sorted output, with the boundary moving left one step per iteration. Nothing else is allocated, which is where the O(1) space comes from.

The array is the tree

For an element at index i in a zero-indexed array, its left child is at 2i+1, its right child at 2i+2, and its parent at ⌊(i−1)/2⌋. That is the entire data structure. There are no node objects and no pointers — the tree exists only as an interpretation of arithmetic on indices.

This representation works because a heap is a *complete* tree: every level is full except possibly the last, which fills left to right. Completeness is what guarantees the index arithmetic has no gaps, and it is why heaps are stored in arrays while general binary trees are not.

A useful consequence: all the leaves occupy the second half of the array. Elements from index ⌊n/2⌋ onwards have no children at all, which is why building a heap only needs to process the first half.

Sift-down: the one operation that matters

Both phases are built from a single primitive. Sift-down takes a node that may be smaller than its children and pushes it into place: compare it with its larger child, swap if the child is bigger, and repeat from the new position until it is larger than both children or it reaches the bottom.

Comparing against the *larger* child is essential. Swapping with the smaller one would put a value above its sibling that might exceed it, breaking the heap property in the process of trying to restore it.

Building the heap means calling sift-down on every non-leaf node, starting from the last one and moving backwards to the root. Processing bottom-up matters: when sift-down runs on a node, both of its subtrees are already valid heaps, which is precisely the precondition the operation requires.

Step-by-step walkthrough

Take [4, 10, 3, 5, 1]. Read as a tree, that is 4 at the root, with children 10 and 3, and 10's children being 5 and 1.

1. Build phase, starting at the last non-leaf (index 1, holding 10). Its children are 5 and 1, both smaller, so nothing moves.
2. Sift-down the root, 4. Its children are 10 and 3; the larger is 10, which is bigger than 4, so swap → [10, 4, 3, 5, 1].
3. Continue sifting 4 from its new position. Its children are 5 and 1; 5 is larger, so swap → [10, 5, 3, 4, 1]. The array is now a valid max-heap.
4. Sort phase: swap the root 10 with the last element → [1, 5, 3, 4, 10]. 10 is final. Heap shrinks to four elements; sift 1 down → [5, 4, 3, 1, 10].
5. Swap root 5 with position 4 → [1, 4, 3, 5, 10], shrink, sift → [4, 1, 3, 5, 10]. Repeat until one element remains: [1, 3, 4, 5, 10].

How the animation above works

The two phases look completely different, which is the clearest thing to watch for. During the build phase, elements move in short hops as sift-downs run on progressively higher nodes, and nothing turns mint because nothing is final yet. Then the sort phase begins and the pattern changes: a large value teleports from position 1 to the far right, a mint bar appears, and a cascade of comparisons walks back down the heap.

That teleport is worth pausing on. It is the reason heap sort is not stable and the reason its cache behaviour is poor — index 0 and index n−1 are nowhere near each other in memory, and neither are a parent and its children once the array is larger than a cache line.

Time complexity

Building the heap: O(n). Counterintuitive but provable, as set out in the callout above — the work is dominated by the many cheap nodes near the leaves rather than the few expensive ones near the root.

The sort phase: O(n log n). Each of the n−1 extractions performs one swap and one sift-down of height at most log₂n.

Total: O(n log n) in the best, average and worst case. Like merge sort, there is no input that degrades it — the structure of the heap bounds every operation regardless of the data. Unlike merge sort, it achieves this in O(1) space.

Heap sort is not adaptive: an already-sorted array costs essentially the same as a random one. There is no cheap way to detect that the input is ordered, because a sorted array is a valid min-heap, which is precisely the wrong shape for extracting maxima.

So why is it not the default?

On paper heap sort dominates: guaranteed O(n log n), O(1) space, no adversarial input. In practice quick sort beats it by a factor of two or three on typical data, and the reason is almost entirely memory locality.

Quick sort's partitioning scans contiguous memory, which CPU prefetchers predict perfectly. Heap sort jumps from index i to 2i+1, which for anything beyond a few thousand elements means a different cache line — often a different page — on nearly every step. A cache miss costs roughly as much as a hundred comparisons, so an algorithm that misses constantly loses badly even with a superior operation count.

It also does about twice as many comparisons as quick sort on average, and it is unstable, so it offers nothing to sorting that merge sort does not do better where stability matters.

Its real home is as the safety net. Introsort — the C++ standard library sort — runs quick sort but tracks recursion depth, and when the depth exceeds about 2·log₂n it switches that branch to heap sort. Quick sort's speed in the common case, heap sort's guarantee in the pathological one. Heap sort is not the algorithm you run; it is the algorithm that makes it safe to run quick sort.

Space and stability

O(1) auxiliary space. The heap lives in the array being sorted, and sift-down is iterative in any sensible implementation, so there is no recursion stack either. This makes heap sort the strongest choice when memory is genuinely constrained and the worst case genuinely matters.

Not stable. The extraction swap moves the last element of the heap to the root, jumping over everything in between — exactly the long-distance movement that breaks the relative order of equal elements. Consider [2a, 2b, 1]: the first extraction swaps the root with position 3, and the two 2s can emerge in either order depending on the heap's internal arrangement.

The same heap machinery, used differently, gives you a priority queue — and that is where heaps genuinely earn their keep. Dijkstra's algorithm, A* search, task schedulers and event simulations all need repeated extraction of the minimum from a changing set, which is exactly what a heap does in O(log n) per operation.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Heap Sort in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Heap sort: guaranteed O(n log n) time and O(1) space.
 * Sift-down is written iteratively so there is no recursion stack either.
 */
function heapSort(arr) {
  const n = arr.length;

  // Phase 1: build a max-heap. Only the first half has children.
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, i, n);
  }

  // Phase 2: the root is the largest, so move it to the sorted tail.
  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]];
    siftDown(arr, 0, end);
  }

  return arr;
}

function siftDown(arr, root, size) {
  for (;;) {
    const left = 2 * root + 1;
    if (left >= size) return;

    // Comparing against the larger child is essential — swapping with the
    // smaller one can leave a value above a bigger sibling.
    let largest = left;
    if (left + 1 < size && arr[left + 1] > arr[left]) largest = left + 1;

    if (arr[root] >= arr[largest]) return;
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    root = largest;
  }
}

console.log(heapSort([4, 10, 3, 5, 1])); // [1, 3, 4, 5, 10]

Advantages and disadvantages

Real-world applications

• The worst-case fallback inside introsort — C++'s std::sort switches to heap sort when quick sort's recursion goes too deep, which is heap sort's most important production role.
• Priority queues, which is the heap structure rather than the sort: task schedulers, event-driven simulation, and bandwidth management.
• Dijkstra's algorithm and A* pathfinding, which need repeated extraction of the minimum-cost node from a changing frontier.
• Finding the k largest or smallest elements of a large stream in O(n log k) using a bounded heap, without storing everything.
• Embedded and real-time systems that need both a hard time bound and no dynamic allocation.
• Operating-system kernels, where predictable worst-case behaviour matters more than average speed.

Interview questions

The questions that actually get asked about Heap Sort, with the answers an interviewer is listening for.

1. Q1. Why is building a heap O(n) rather than O(n log n)?

   Because sift-down's cost is proportional to the node's height, not the tree's, and most nodes are short. Half the nodes are leaves and cost nothing; a quarter are one level up and cost at most one swap; an eighth cost two. Summing n/4·1 + n/8·2 + n/16·3 + … gives a series that converges to n. The naive bound of n nodes × log n height is a real upper bound, just not a tight one.

2. Q2. Heap sort has better worst-case complexity than quick sort. Why is quick sort still preferred?

   Cache behaviour. Quick sort scans contiguous memory, which prefetchers handle perfectly; heap sort jumps from i to 2i+1, missing the cache on nearly every step once the array exceeds cache size. A miss costs about as much as a hundred comparisons. Heap sort also does roughly twice as many comparisons and is unstable, so in practice quick sort wins by two to three times.

3. Q3. Why must sift-down compare against the larger child?

   Because the promoted child becomes the parent of the other one. If you swap with the smaller child, the value now sitting at the parent position may be less than its sibling, which violates the heap property you were trying to restore — and the violation is invisible from the path sift-down is walking, so it never gets corrected.

4. Q4. Is heap sort stable, and can it be made stable?

   No. The extraction step swaps the root with the last element of the heap, moving a value across the entire array and past any equal elements in between. It can be made stable by augmenting each element with its original index and breaking ties on it, but that costs O(n) extra memory — and at that point merge sort is the better tool.

5. Q5. How would you find the 10 largest elements in a stream of a million numbers?

   Keep a min-heap of size 10. For each incoming value, compare it against the heap's root — the smallest of the current top 10. If it is larger, replace the root and sift down. That is O(n log k) time and O(k) space, and it never requires holding the stream in memory, which sorting the whole input would.

Common mistakes

• Comparing against the left child only, or against the smaller child, which corrupts the heap in ways that produce almost-sorted output.
• Starting the build loop at n−1 instead of ⌊n/2⌋−1 — harmless for correctness but it wastes work sifting leaves that have no children.
• Forgetting to shrink the heap size in the extraction phase, so sift-down walks back into the already-sorted tail and undoes it.
• Using 2*i and 2*i+1 for children, which is the one-indexed formula, in a zero-indexed array.
• Building a min-heap when sorting ascending — a max-heap is what you want, because extraction fills the array from the right.
• Writing sift-down recursively without noticing it can be a simple loop, which adds O(log n) stack for no benefit.
• Checking left + 1 < size incorrectly and reading a right child that lies outside the current heap boundary.

Optimisation tips

• Write sift-down iteratively rather than recursively — it is naturally tail-recursive, and the loop version uses no stack.
• Use Floyd's 'sift-down then sift-up' variant: walk the element all the way to a leaf without comparing it, then sift it back up. This roughly halves the comparison count, since most elements end up near the bottom anyway.
• For k-largest problems, do not sort at all — heapify in O(n) and extract only k times, giving O(n + k log n).
• Prefer std::make_heap/std::sort_heap or your language's built-in heap over a hand-rolled one for production; they are tuned and correct.
• If the priority queue rather than the sort is what you need, keep the heap and skip phase two entirely — that is the more common real use.
• Use heap sort as a fallback behind quick sort rather than as a primary sort, which is exactly what introsort does.

Summary

Heap sort reinterprets the array as a complete binary tree, builds a max-heap in O(n), then repeatedly swaps the root to the end of the array and restores the heap over the shrinking front section. The result is O(n log n) in every case with O(1) extra space — the only common algorithm that offers both.

It loses to quick sort in practice because the parent-to-child index jumps destroy cache locality, and it loses to merge sort where stability is needed. Its genuine value is twofold: as the worst-case guarantee behind introsort, and as the priority queue that Dijkstra's algorithm and every task scheduler depends on. Learn the heap; the sort is the smaller half of what you get.

Frequently asked questions

Related algorithms

• Merge Sort

  Split the array down to single elements, then merge sorted halves back together.

  O(n log n)Intermediate

• Quick Sort

  Partition around a pivot so everything smaller lands left and larger lands right.

  O(n log n)Intermediate

• Selection Sort

  Scan for the smallest remaining value and swap it into place — one swap per pass.

  O(n²)Beginner