How heap sort works
Heap sort never builds a tree out of pointers. It reads the array itself as a binary tree: index 0 is the root, and the children of index i are 2i + 1 and 2i + 2. That is why the visualizer draws the same numbers twice, as a tree on top and as bars below. A swap in one is the same swap in the other.
A max-heap is that tree with one rule: every parent is at least as big as its children. Nothing else is ordered, but the rule forces the largest value to the root. Think of an office hierarchy where every manager outranks their own team: the top person outranks everyone, even though two teams are never compared directly.
Phase 1 builds the heap bottom-up. Leaves are already tiny heaps, so it starts at the last parent, n/2 − 1, and walks back to the root. At each parent it calls sift_down: compare the value with its children and, if a child is bigger, swap with the bigger child and keep going down. This phase costs O(n), not O(n log n), because most nodes sit near the bottom and can only fall a level or two.
Phase 2 sorts. The root is the largest value, so swap it with the last value of the heap. That value is now in its final place, and the heap shrinks by one. The value that landed on the root is usually small, so sift it down to repair the heap. After n − 1 rounds the array is sorted. Each repair costs at most one walk from root to leaf, about log₂ n levels, which gives O(n log n) in every case.
The algorithm in 5 steps
- 1 Read the array as a tree: the children of index
iare2i + 1and2i + 2. - 2 For every parent from
n/2 − 1down to 0, sift its value down: swap it with its bigger child until neither child is bigger. The array is now a max-heap. - 3 Swap the root, the largest value in the heap, with the last value in the heap. That index is now final.
- 4 Shrink the heap by one and sift the new root down to restore the heap rule.
- 5 Repeat steps 3 and 4 until the heap holds one value. The array is sorted.
Worked example
Here is the full run on a fixed array, generated by the same code as the visualizer. The first row is the end of phase 1, when the array has become a max-heap. Each row after that is one root swap: the largest value left goes to its final place. The sift-down steps in between are counted in the total but not listed.
Input: [12, 31, 7, 25, 18, 3]
- Step 17 Phase 1 done: the array is a max-heap, so the largest value, 31, is at the root (index 0). Phase 2: swap the root to the end, shrink the heap by one, repair it, repeat. 3125712183
- Step 18 Swap the root 31 (the largest value left) with 3 at index 5. 31 is now final at index 5; the heap shrinks to indices 0–4. 3257121831
- Step 26 Swap the root 25 (the largest value left) with 3 at index 4. 25 is now final at index 4; the heap shrinks to indices 0–3. 3187122531
- Step 33 Swap the root 18 (the largest value left) with 3 at index 3. 18 is now final at index 3; the heap shrinks to indices 0–2. 3127182531
- Step 38 Swap the root 12 (the largest value left) with 7 at index 2. 12 is now final at index 2; the heap shrinks to indices 0–1. 7312182531
- Step 41 Swap the root 7 with 3 at index 1. 7 is final at index 1, and 3, the smallest value, is left at index 0: sorted. 3712182531
Total for this run: 17 comparisons and 12 swaps, in 42 animation steps. Result: 3, 7, 12, 18, 25, 31.
Time and space complexity
Best
O(n log n)With distinct values, every root swap brings a small value to the top that must sift back down. Even sorted input pays the full cost. Only an array where every value is equal finishes in O(n).
Average
O(n log n)n − 1 repairs, each walking at most log₂ n levels with two comparisons per level, plus an O(n) build.
Worst
O(n log n)No input can make it quadratic. Sedgewick and Wayne bound it at under 2n log₂ n + 2n comparisons.
Space
O(1)The heap lives inside the array. The sift-down here is a loop, so there is no recursion stack either.
- Stable:
- No
- In place:
- Yes
- Adaptive:
- No
- Worst case:
- O(n log n)
Six sorts, same 8 numbers
Comparison counts from running each algorithm on the visualizer's array, then on the same numbers already sorted and in reverse order. Computed from the code on these pages, not typed in.
| Algorithm | Comparisons | Moves | Sorted input | Reversed input |
|---|---|---|---|---|
| Insertion sort | 17 | 13 shifts | 7 | 28 |
| Selection sort | 28 | 5 swaps | 28 | 28 |
| Bubble sort | 25 | 13 swaps | 7 | 28 |
| Merge sort | 16 | 24 writes | 12 | 12 |
| Quick sort | 38 | 5 swaps | 31 | 32 |
| Heap sort | 26 | 19 swaps | 27 | 24 |
The last two columns are comparisons too. Exact counts depend on the input and the variant (this page's heap sort builds its heap bottom-up and counts both child comparisons on every level of a sift), which is why complexity is stated as growth, not exact numbers.
When to use it, and when not to
Good fit
- You need a guaranteed O(n log n) with no extra memory. The Linux kernel's generic sort() in lib/sort.c is a heapsort for exactly this reason: its comments say quicksort's O(n²) worst case can be exploited and its extra memory needs suit the kernel less.
- As a safety net inside a faster sort. GCC's std::sort is an introsort: it runs quick sort, and if the recursion goes deeper than 2·log₂ n it switches that part to heap sort, so the worst case stays O(n log n).
- You only need the top k values in order: build the heap in O(n), then stop after k root swaps, O(n + k log n) in total.
- Learning priority queues: the same sift-down and the same index arithmetic run Python's heapq, Java's PriorityQueue and every scheduler built on a binary heap.
Pick something else when
- You need a stable sort, for example sorting records by a second key after a first. Use merge sort or your language's built-in stable sort.
- Raw speed on large arrays of numbers. A well-tuned quick sort usually wins in practice: it makes fewer comparisons on average and reads memory in order, while heap sort jumps from index i to 2i + 1 and misses the CPU cache.
- Nearly sorted data. Heap sort does the same O(n log n) work anyway, while insertion sort or Timsort finish in close to O(n).
- Linked lists. Finding the children of a node needs indexing by position, which a linked list cannot do in O(1). Merge sort is the natural fit.
Common mistakes and bugs
-
1.Using 1-based child formulas on a 0-based array
Textbooks that start the heap at index 1 use children
2iand2i + 1, parenti // 2. In a 0-based array that makes index 0 its own child. With index 0 as the root, the children are2i + 1and2i + 2and the parent is(i − 1) // 2. -
2.Building the heap from the root downwards
Sift-down only works when both subtrees are already heaps, so the build loop must run from the last parent back to 0. Running it from 0 forwards fails: on
[1, 2, 3, 4]it produces[3, 4, 1, 2], where the root 3 is smaller than its child 4. -
3.Forgetting to shrink the heap
After swapping the root to index
end, callsift_down(a, 0, end), notsift_down(a, 0, n). With the full size, the sift can pull the values you just put in their final places back into the heap. -
4.Swapping with the left child by default
The parent must swap with the bigger child. Swapping with the left one when the right one is bigger puts a smaller value above the right child and breaks the heap rule. Compare both children first, then swap once.
-
5.Using a min-heap to sort ascending in place
A min-heap puts the smallest value at the root, and swapping it to the end of the array builds the result in descending order. For ascending order in place, use a max-heap. Popping a min-heap into a new list also works, but it needs O(n) extra space.
Interview questions
Try answering before you open the model answer.
Q1 Why does building a heap take O(n) and not O(n log n)?
Model answer: Sift-down costs at most the height of the node, and most nodes are low. Half the nodes are leaves and cost nothing, a quarter can fall one level, an eighth two, and so on. The total, n/4 · 1 + n/8 · 2 + n/16 · 3 + ..., stays below n swaps, and Sedgewick and Wayne bound the comparisons at under 2n.
Q2 Heap sort is O(n log n) in the worst case and quick sort is not. Why is quick sort usually preferred?
Model answer: Quick sort makes about 1.39 n log₂ n comparisons on average, heap sort close to 2 n log₂ n. Quick sort also scans memory in order, while heap sort jumps from i to 2i + 1, which misses the cache on large arrays. Libraries get both: introsort runs quick sort and falls back to heap sort if recursion gets too deep.
Q3 Why is heap sort not stable? Show an example.
Model answer: Root swaps move values across long distances. Take [5, 5, 2] and call the 5s A and B. The array is already a heap. Swapping the root puts A last: [2, B, A]. Sifting 2 down gives [B, 2, A], and the next root swap gives [2, B, A]. The two 5s finish in reverse order.
Q4 Find the k largest values in an array of n values.
Model answer: Keep a min-heap of size k: push each value, and once the heap holds more than k values pop the smallest. That is O(n log k) time and O(k) space, and it works on a stream. If the whole array is in memory, heapify it as a max-heap in O(n) and pop k times, O(n + k log n).
Q5 How is heap sort related to selection sort?
Model answer: Both repeatedly take the extreme value of the unsorted part and put it in its final place. Selection sort finds it by scanning, O(n) per pass, O(n²) in total. Heap sort keeps the unsorted part as a max-heap, so the largest value is always at the root and each repair is O(log n), O(n log n) in total.
Frequently asked questions
What is the time complexity of heap sort?
O(n log n) in the best, average and worst case, with O(1) extra space. Building the max-heap takes O(n). Each of the n − 1 root swaps is followed by a sift-down of at most log₂ n levels. Unlike quick sort, no input can make it quadratic; only an array of all-equal values finishes in O(n).
Is heap sort stable?
No. Swapping the root with the last value of the heap moves values over long distances, so equal values can change order. In [5, 5, 2], the first 5 ends up after the second one. If you need stability, use merge sort, or sort pairs of (value, original index) so that no two keys are equal.
Is heap sort an in-place sorting algorithm?
Yes. The heap is stored in the array itself: the parent of index i is (i − 1) // 2 and its children are 2i + 1 and 2i + 2, so no tree nodes or pointers are needed. With an iterative sift-down, as in the code on this page, the extra memory is a few index variables: O(1).
Why does heap sort use a max-heap for ascending order?
Because the largest value has to go to the end of the array first. A max-heap keeps the largest value at the root, so each round swaps it into the last free slot and the sorted part grows from the right. A min-heap would put the smallest value at the end and sort the array in descending order.
Is heap sort faster than quick sort?
Usually not in practice, even though its worst case is better. Heap sort makes more comparisons on average and jumps around memory, which is slow on large arrays. That is why libraries such as GCC's std::sort use quick sort first and switch to heap sort only when the recursion gets too deep.