Heap Sort: Heapify, Sift Down and Cost
Build a max-heap in the array itself, then repeatedly swap the root to the end and restore the heap over what remains.
The Array Is the Tree
Heap sort needs no node objects and no pointers. A plain array is a complete binary tree if you read the indices arithmetically: the children of index i sit at 2i+1 and 2i+2, and the parent of i is at ⌊(i−1)/2⌋.
A max-heap adds one rule: every parent is greater than or equal to both its children. This is much weaker than being sorted — siblings have no defined order — but it guarantees the single thing the algorithm needs: the maximum is at index 0.
So the array does double duty. The front is a heap; the back is the sorted output growing leftward. No auxiliary structure is ever allocated, which is where heap sort's O(1) space comes from.
- children(i) = 2i+1, 2i+2; parent(i) = ⌊(i−1)/2⌋
- Max-heap: every parent ≥ both children
- A heap is not sorted — only the root is guaranteed
- Indices past ⌊n/2⌋−1 are leaves and trivially satisfy the property
Sift Down
Sift down is the one operation everything else is built from. Given a node whose children are already valid heaps but which may itself be too small:
- Find the larger child compare the two children and pick the bigger one. Not the left one, not the smaller one.
- Compare if the node is already at least as large as that child, stop. The subtree is a valid heap.
- Swap and descend otherwise exchange the node with that larger child and continue from the child's position.
- Repeat until the node fits or reaches a leaf. Each step descends one level, so the cost is O(log n).
Comparing against the larger child is essential. Swapping with the smaller one would place a value above its sibling that may exceed it, breaking the property you just tried to fix — a classic exam trap.
Each step descends one level, so sift down costs O(log n) in the worst case. The mirror operation, sift up, is used for insertion into a heap but is not needed by heap sort, which only ever removes from the root.
- Always compare against the larger of the two children
- Swap and continue downward until the node fits or becomes a leaf
- Cost is the height of the subtree: O(log n)
- Heap sort never needs sift up — only removal from the root
Sort with heap sort
def heap_sort(values):
n = len(values)
# build a max-heap: start at the last parent and work backwards
for i in range(n // 2 - 1, -1, -1):
sift_down(values, i, n)
# repeatedly move the root to the end and shrink the heap
for end in range(n - 1, 0, -1):
values[0], values[end] = values[end], values[0]
sift_down(values, 0, end)
return values
def sift_down(values, i, size):
while True:
largest = i
left, right = 2 * i + 1, 2 * i + 2
if left < size and values[left] > values[largest]:
largest = left
if right < size and values[right] > values[largest]:
largest = right
if largest == i: # the node already fits
return
values[i], values[largest] = values[largest], values[i]
i = largest
print(heap_sort([4, 10, 3, 5, 1]))
#include <iostream>
#include <vector>
void siftDown(std::vector<int>& values, int i, int size) {
while (true) {
int largest = i;
const int left = 2 * i + 1, right = 2 * i + 2;
if (left < size && values[left] > values[largest]) largest = left;
if (right < size && values[right] > values[largest]) largest = right;
if (largest == i) return; // the node already fits
std::swap(values[i], values[largest]);
i = largest;
}
}
void heapSort(std::vector<int>& values) {
const int n = static_cast<int>(values.size());
for (int i = n / 2 - 1; i >= 0; --i) siftDown(values, i, n);
for (int end = n - 1; end > 0; --end) {
std::swap(values[0], values[end]);
siftDown(values, 0, end);
}
}
int main() {
std::vector<int> values {
4, 10, 3, 5, 1
};
heapSort(values);
for (int v : values) std::cout << v << ' ';
std::cout << '\n';
}import java.util.Arrays;
public class HeapSort {
static void siftDown(int[] values, int i, int size) {
while (true) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < size && values[left] > values[largest]) largest = left;
if (right < size && values[right] > values[largest]) largest = right;
if (largest == i) return; // the node already fits
int tmp = values[i];
values[i] = values[largest];
values[largest] = tmp;
i = largest;
}
}
static void heapSort(int[] values) {
int n = values.length;
for (int i = n / 2 - 1; i >= 0; i--) siftDown(values, i, n);
for (int end = n - 1; end > 0; end--) {
int tmp = values[0];
values[0] = values[end];
values[end] = tmp;
siftDown(values, 0, end);
}
}
public static void main(String[] args) {
int[] values = {4, 10, 3, 5, 1};
heapSort(values);
System.out.println(Arrays.toString(values));
}
}Step through it
Running on [4, 10, 3, 5, 1]
On paper: Build Heap and Extract
Take [4, 10, 3, 5, 1]. Build-heap starts at index ⌊n/2⌋−1 = 1 and works backwards to 0 — everything after index 1 is a leaf and already valid.
- Build, index 1 value 10, children 5 and 1. Already the largest, so nothing moves.
- Build, index 0 value 4, children 10 and 3. Swap with 10 →
[10, 4, 3, 5, 1]. - Build, continue down 4 now sits at index 1 with children 5 and 1. Swap with 5 →
[10, 5, 3, 4, 1]. Valid max-heap. - Extract swap the root with the last element →
[1, 5, 3, 4 | 10]. 10 is finished and leaves the heap. - Sift the new root down 1 against larger child 5, swap; then against 4, swap →
[5, 4, 3, 1 | 10].
Repeat the extract step until one element remains. Marking the sorted suffix with a bar at each stage is what makes an exam answer readable — it shows the heap shrinking and the output growing in the same array.
- Start build-heap at ⌊n/2⌋−1, not at 0 or n−1
- Work backwards so children are valid before their parent
- Extraction shrinks the heap by one and grows the sorted tail
- Always sift the swapped-in value down over the remaining heap
Why Build-Heap Is O(n)
The obvious estimate is n sift-downs at O(log n) each, giving O(n log n). That bound is correct but not tight, and the real answer is O(n).
The reason is that most nodes are near the bottom, where sift down has almost nowhere to go. Half the nodes are leaves and cost nothing; a quarter sit one level up and cost at most one swap; an eighth cost at most two. Summing height × count over all levels gives Σ n/2^(h+1) · h, which converges to less than n.
Only the few nodes near the root pay the full log n, and there are very few of them. So building the heap is Θ(n), and the O(n log n) total comes entirely from the extraction phase: n removals at O(log n) each. Stating that split — Θ(n) to build, Θ(n log n) to extract — is what a complete answer looks like.
| Phase | Operations | Cost each | Total |
|---|---|---|---|
| Build heap | n/2 sift downs | O(log n) worst, O(1) typical | Θ(n) |
| Extract | n−1 swaps + sift downs | O(log n) | Θ(n log n) |
| Overall | Θ(n log n) |
- Most nodes are leaves, so most sift-downs are trivial
- Σ n/2^(h+1) · h converges to less than n
- Build is Θ(n); extraction dominates at Θ(n log n)
- The bound holds on every input — there is no worst case
The Trade Against Quick Sort
Heap sort's guarantee is unusually strong: O(n log n) on every input, in O(1) space, with no recursion. Merge sort matches the time but needs O(n) memory; quick sort matches the space but can degrade to O(n²).
Despite that, quick sort is usually faster in practice, and the reason is memory access. Quick sort's partition walks contiguous memory, which prefetchers and caches reward. Heap sort jumps between index i and 2i+1 — strides that grow with the array and defeat the cache once the data exceeds it. It also does more swaps and has less predictable branches.
So heap sort's real niche is where the guarantee matters more than the constant: hard real-time systems that cannot risk O(n²), memory-constrained environments with no room for a merge buffer, and as the safety net inside introsort, where quick sort switches to it once recursion runs too deep. Note also that it is not stable — the long-range root swap moves values past equal keys, the same defect selection sort has.
- Guaranteed O(n log n) in O(1) space, with no recursion
- Poor cache behaviour is why quick sort usually beats it
- Used as introsort's fallback to cap the worst case
- Not stable — the root swap jumps over equal keys