Heap Sort
Selection sort finds the maximum n times by scanning; heap sort finds it n times by keeping the array arranged as a heap, where the maximum is always at index 0 and restoring that after a removal costs only log n. The heap lives inside the array itself, children of i at 2i + 1 and 2i + 2, so no extra memory is needed: the sorted values accumulate at the right end as the heap shrinks from the left.
Sort 8 values with a heap built in place. Read the array as a tree: the children of index i sit at 2i + 1 and 2i + 2. First make every parent larger than its children, then pull the maximum off the top 8 times.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 16, with their answers.
Parent 5 at index 3, larger child 2. What happens?
Answer: Stop, the parent is larger. The parent already wins.
Parent 3 at index 2, larger child 8. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 10 at index 1, larger child 5. What happens?
Answer: Stop, the parent is larger. The parent already wins.
Parent 4 at index 0, larger child 10. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 4 at index 1, larger child 5. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 4 at index 3, larger child 2. What happens?
Answer: Stop, the parent is larger. The parent already wins.
Parent 2 at index 0, larger child 8. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 2 at index 2, larger child 7. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 2 at index 0, larger child 7. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 2 at index 2, larger child 3. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 2 at index 0, larger child 5. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 2 at index 1, larger child 4. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 1 at index 0, larger child 4. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 1 at index 1, larger child 2. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 1 at index 0, larger child 3. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
Parent 1 at index 0, larger child 2. What happens?
Answer: Swap with the larger child. The child is larger, so the parent sinks.
How it runs, step by step
Sort 8 values with a heap built in place. Read the array as a tree: the children of index i sit at 2i + 1 and 2i + 2. First make every parent larger than its children, then pull the maximum off the top 8 times.
Heap sort on 4, 10, 3, 5, 1, 8, 7, 2.
Index 3 holds 5; its larger child is 2 at index 7. 5 is already at least as large, so the heap property holds here.
Parent 5 at 3, larger child 2 at 7. Stop.
Index 2 holds 3; its larger child is 8 at index 5. 8 > 3, so they swap and 3 sinks to index 5.
Parent 3 at 2, larger child 8 at 5. Swap.
Index 1 holds 10; its larger child is 5 at index 3. 10 is already at least as large, so the heap property holds here.
Parent 10 at 1, larger child 5 at 3. Stop.
Index 0 holds 4; its larger child is 10 at index 1. 10 > 4, so they swap and 4 sinks to index 1.
Parent 4 at 0, larger child 10 at 1. Swap.
Index 1 holds 4; its larger child is 5 at index 3. 5 > 4, so they swap and 4 sinks to index 3.
Parent 4 at 1, larger child 5 at 3. Swap.
Index 3 holds 4; its larger child is 2 at index 7. 4 is already at least as large, so the heap property holds here.
Parent 4 at 3, larger child 2 at 7. Stop.
Every parent beats its children: a max-heap, with the maximum 10 at index 0.
Max-heap built, maximum 10.
Swap the root 10 with the last heap slot, index 7. 10 is now in its final place and the heap shrinks to 7 slots. The new root must sift down.
10 moves to index 7, heap size 7.
Index 0 holds 2; its larger child is 8 at index 2. 8 > 2, so they swap and 2 sinks to index 2.
Parent 2 at 0, larger child 8 at 2. Swap.
Index 2 holds 2; its larger child is 7 at index 6. 7 > 2, so they swap and 2 sinks to index 6.
Parent 2 at 2, larger child 7 at 6. Swap.
Swap the root 8 with the last heap slot, index 6. 8 is now in its final place and the heap shrinks to 6 slots. The new root must sift down.
8 moves to index 6, heap size 6.
Index 0 holds 2; its larger child is 7 at index 2. 7 > 2, so they swap and 2 sinks to index 2.
Parent 2 at 0, larger child 7 at 2. Swap.
Index 2 holds 2; its larger child is 3 at index 5. 3 > 2, so they swap and 2 sinks to index 5.
Parent 2 at 2, larger child 3 at 5. Swap.
Swap the root 7 with the last heap slot, index 5. 7 is now in its final place and the heap shrinks to 5 slots. The new root must sift down.
7 moves to index 5, heap size 5.
Index 0 holds 2; its larger child is 5 at index 1. 5 > 2, so they swap and 2 sinks to index 1.
Parent 2 at 0, larger child 5 at 1. Swap.
Index 1 holds 2; its larger child is 4 at index 3. 4 > 2, so they swap and 2 sinks to index 3.
Parent 2 at 1, larger child 4 at 3. Swap.
Swap the root 5 with the last heap slot, index 4. 5 is now in its final place and the heap shrinks to 4 slots. The new root must sift down.
5 moves to index 4, heap size 4.
Index 0 holds 1; its larger child is 4 at index 1. 4 > 1, so they swap and 1 sinks to index 1.
Parent 1 at 0, larger child 4 at 1. Swap.
Index 1 holds 1; its larger child is 2 at index 3. 2 > 1, so they swap and 1 sinks to index 3.
Parent 1 at 1, larger child 2 at 3. Swap.
Swap the root 4 with the last heap slot, index 3. 4 is now in its final place and the heap shrinks to 3 slots. The new root must sift down.
4 moves to index 3, heap size 3.
Index 0 holds 1; its larger child is 3 at index 2. 3 > 1, so they swap and 1 sinks to index 2.
Parent 1 at 0, larger child 3 at 2. Swap.
Swap the root 3 with the last heap slot, index 2. 3 is now in its final place and the heap shrinks to 2 slots. The new root must sift down.
3 moves to index 2, heap size 2.
Index 0 holds 1; its larger child is 2 at index 1. 2 > 1, so they swap and 1 sinks to index 1.
Parent 1 at 0, larger child 2 at 1. Swap.
Swap the root 2 with the last heap slot, index 1. 2 is now in its final place and the heap shrinks to 1 slot. The new root must sift down.
2 moves to index 1, heap size 1.
Sorted. 27 comparisons and 20 swaps. Building the heap is O(n) and each of the n extractions sifts down at most log n levels: O(n log n) in every case, in place, but not stable.
Sorted after 27 comparisons and 20 swaps.
Write it yourself
Define heapSort(values) and return the same values in ascending order. It runs in your browser against this lesson's own 2 examples.
// Build a max-heap in place, then repeatedly swap the root to the end and sift down what is left.function heapSort(values) { return values;}
Remember
- Children of index i live at 2i + 1 and 2i + 2, so the heap needs no pointers and no extra array.
- Build the heap bottom up in O(n), then swap the root to the end and sift down, n times.
- O(n log n) on every input and in place, but a sift can jump equal keys past each other: not stable.
Topics covered
Where this is used
Operating systemsThe Linux kernel's sort()
lib/sort.c, the sort routine the rest of the kernel calls, is a heap sort, and its comments say so. Kernel code runs on a stack of a couple of pages and cannot risk an unplanned recursion depth, and it cannot allocate a scratch buffer on a path that may itself be handling memory pressure. Heap sort buys an O(n log n) bound while asking for neither: merge sort wants the buffer, and the file's own header comment gives quicksort's stack usage as the reason it was not chosen.
Standard librariesIntrosort, quicksort's safety net
C++ requires std::sort to be O(n log n) in the worst case, which plain quicksort is not: a crafted input can drive it to n squared. libstdc++ and libc++ count recursion depth and, once it passes roughly 2 log2 n, abandon quicksort and heap sort whatever subrange is left. Java's DualPivotQuicksort switches once its recursion counter passes a fixed cap, and Go's pdqsort after about log2 n badly balanced partitions. Heap sort is what they all switch to because it can take over a half-finished partition in place, with no setup and no allocation.
Databasestop-N heapsort in PostgreSQL
For ORDER BY ... LIMIT 10 across a million rows, PostgreSQL does not sort the million. It keeps a heap of ten, and each incoming row is either worse than the root and thrown away or replaces the root and sifts down. EXPLAIN ANALYZE names this mode 'top-N heapsort', and the win is memory rather than comparisons: work_mem holds ten tuples instead of a million, which keeps the sort in RAM instead of spilling to disk.
Systems programmingheapsort(3) in BSD libc
FreeBSD and macOS ship three sorts side by side and let the caller choose. The manual page puts the trade bluntly: mergesort needs a buffer of nmemb * size bytes and should be used only when space is not at a premium, and heap sort's only advantage over qsort is that it uses almost no additional memory, because qsort allocates nothing but is implemented with recursion. A daemon sorting inside a fixed memory budget, with no room for a scratch buffer or an unbounded call stack, is the case that third entry exists for.
Why it works this way
Why the build starts at n / 2 - 1 and walks backwards
Every index from n / 2 onward is a leaf, and a leaf is already a valid one-element heap, so the first index that can possibly need fixing is n / 2 - 1. The direction matters more than the starting point: siftDown is only correct when both subtrees of p are already heaps, and counting down to 0 guarantees that, because a child's index is always larger than its parent's. Run the same loop forwards and you sift nodes whose subtrees are still broken, which leaves the array unsorted with no error anywhere.
Why the build is O(n) but the sorting loop is not
The build performs n / 2 sift-downs and the sorting loop n - 1, so the count is linear either way and the whole difference is how far each one travels. During the build half the nodes are leaves and sink zero levels, a quarter sink at most one, an eighth at most two, and n/4 * 1 + n/8 * 2 + n/16 * 3 + ... converges to n. In the sorting loop every sift starts at the root, where the full log n drop is always available, so nothing collapses. This is also why the build sifts down rather than inserting values one at a time: sift-up is slowest exactly where most of the nodes are, at the bottom.
The size passed to siftDown has to shrink
The call is siftDown(a, 0, end), not end + 1, because the value just parked at index end must fall outside the heap so that nothing can move it again. Passing n instead compiles, runs and produces a plausible-looking array: every value the loop has already placed is still inside the heap, so later sifts pull them back out of their final positions. Nothing shrinks physically here - the array is the same array throughout, and the only thing separating the sorted tail from the heap is that one argument.
Why quicksort still wins in practice
On random input both run in n log n time with small constants, yet heap sort is the slower one on real hardware. Quicksort's partition walks two pointers through contiguous memory and uses every cache line it loads; a sift-down jumps from i to 2i + 1, so once the heap outgrows the cache, nearly every level down is a miss. It also does about 2n log2 n comparisons on random input where quicksort averages around 1.39n log2 n, and it is not adaptive: an already sorted array costs about as much as a shuffled one. That combination is why libraries keep heap sort as the fallback rather than the default.
Read more
- HeapsortWikipedia
- IntrosortWikipedia
- lib/sort.c, the kernel's heap sortLinux kernel · git.kernel.org
- qsort, mergesort and heapsort comparedFreeBSD manual · man.freebsd.org
- Heap sort visualisedUSF