Heapsort explained: building, sifting and sorting in place
Heap-based sorting has been a cornerstone of algorithm teaching since the 1960s, prized for its guaranteed O(n log n) runtime and its clever use of a single array to store the structure. Unlike merge sort, it needs no auxiliary buffer; unlike quicksort, it avoids worst-case degradation. For learners in Sydney, Melbourne or Brisbane preparing for technical interviews at firms like Atlassian or Canva, mastering the heapsort workflow — build, sift, swap, repeat — is a near-universal expectation on the whiteboard.
This guide walks through the data structure, the index arithmetic, the sift-down mechanics and the final in-place swap phase. Along the way, we will contrast heapsort with its two closest rivals, examine the way modern CPUs cache their accesses, and note a few practical pitfalls that catch developers working in Python, C or Go on Australian software teams.
Understanding the binary heap as a tree
A binary heap is a nearly complete binary tree where every parent satisfies the heap property: in a max-heap, each parent is greater than or equal to both children; in a min-heap, the relation is reversed. The "nearly complete" qualifier simply means every level is full except possibly the last, which fills from left to right. This shape is what lets a heap be packed densely into contiguous memory without gaps.
The heap property is a partial order rather than a total one. There is no requirement that the left child be smaller than the right child, or that siblings follow any specific ordering between themselves. The only invariant is the parent-child relation. This weak ordering is exactly what gives heaps their strength: insertion and extraction can be done in logarithmic time while keeping the structure balanced, which is why heaps back schedulers, priority queues and the Dijkstra shortest-path algorithm used in route-planning tools across Sydney's transport apps to Melbourne's delivery networks.
Array representation and index arithmetic
Because the heap is nearly complete, it can be stored in a plain array with no pointers at all. For a node at index i (zero-based), the parent sits at ⌊(i − 1) / 2⌋, the left child at 2i + 1 and the right child at 2i + 2. This arithmetic is the secret sauce of heapsort: every navigation step is a couple of integer operations, with no pointer chasing, no allocation overhead and no cache misses on the tree edges.
The trade-off is that heap operations do not generalise to arbitrary trees. If you need a doubly linked or circular structure, the array approach collapses and you reach for explicit pointers. Readers experimenting with such variants may find a walkthrough of a circular doubly linked list instructive as a contrast, because it shows how pointer-rich structures trade locality for flexibility. For heaps, the array wins on locality every time, which matters on the cold-cache workloads common in analytics pipelines run from Perth data centres and Hobart research labs.
Building a max-heap in linear time
A naive approach would push each element through a sift-up operation, costing O(n log n). A smarter approach observes that leaves are already valid one-element heaps, so we only need to sift down on the first n/2 nodes, starting from the last internal node and walking backwards to the root. This bottom-up build runs in O(n) time, a counter-intuitive result that often surprises students preparing for graduate algorithm courses at the University of Melbourne or UNSW.
The intuition is that most nodes sit near the bottom of the tree, where the sift-down has very little distance to travel. A node at depth d moves at most d levels, and there are roughly n / 2^d nodes at that depth. Summing across depths yields a linear bound. Once the build phase finishes, the array satisfies the max-heap property everywhere, and the largest element sits at index 0, ready to be extracted.
The sift-down operation in detail
Sift-down, sometimes named heapify, restores the heap property at a single node by repeatedly promoting the larger of its two children whenever that child is larger than the parent itself. The pseudo-code is short: find the left child, check whether the right child is larger, swap the parent with the larger child if the invariant is broken, then recurse into the child's new position.
sift_down(arr, n, i):
largest = i
left = 2*i + 1
right = 2*i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
swap arr[i], arr[largest]
sift_down(arr, n, largest)
The recursion terminates when the node either has no children or is already larger than both. In a tight C or Rust implementation, sift-down is often written iteratively to dodge function-call overhead, which is why low-latency trading systems in Sydney's financial district still reach for heapsort when deterministic latency matters more than average throughput.
Heapsort compared with quicksort and mergesort
Choosing a sort in production code is rarely about the asymptotic class alone. Heapsort, quicksort and mergesort all hit O(n log n) in the typical case, yet their memory footprint, stability, constant factors and cache friendliness differ enough to change the decision.
| Algorithm | Best / Average / Worst Time | Auxiliary Space | Stable | In-place |
|---|---|---|---|---|
| Heapsort | O(n log n) / O(n log n) / O(n log n) | O(1) | No | Yes |
| Quicksort | O(n log n) / O(n log n) / O(n²) | O(log n) stack | No | Yes |
| Mergesort | O(n log n) / O(n log n) / O(n log n) | O(n) | Yes | No |
| Timsort | O(n) / O(n log n) / O(n log n) | O(n) | Yes | No |
Heapsort wins on worst-case guarantees and memory frugality; quicksort wins on average throughput and cache behaviour; mergesort wins on stability and predictable runtime. Timsort, the default in Python and Java, blends an insertion-sort pass with a merge-sort drive and is the right answer whenever the input contains natural runs of sorted data, which is common in log files exported from Australian financial systems.
The complete heapsort procedure
Heapsort stitches three phases together. First, build a max-heap across the whole array. Second, swap the root (the maximum) with the last element and shrink the heap by one. Third, sift down the new root to restore the heap property on the reduced heap. Repeat the swap-and-sift dance until the heap shrinks to a single element. What remains in the array, reading left to right, is the sorted sequence.
heapsort(arr):
n = length(arr)
for i from n/2 - 1 down to 0:
sift_down(arr, n, i)
for i from n - 1 down to 1:
swap arr[0], arr[i]
sift_down(arr, i, 0)
The crucial observation is that the sorted region grows from the right while the heap region shrinks from the right, and they share the same array. No auxiliary buffer is ever allocated; the algorithm is genuinely in-place. A common implementation mistake is forgetting to pass the current heap size to sift-down rather than the full array length, which corrupts the sorted tail once the first swap is performed. Walking through small examples on paper, say sorting the eight postcodes of a Brisbane delivery route, is the fastest way to internalise the boundary movement.
Complexity, cache behaviour and practical use
Heapsort runs in O(n log n) time in every case: best, average and worst. It uses O(1) auxiliary space beyond the input array, which lets it sort multi-gigabyte datasets on machines where merge sort's buffer would not fit. Its main weakness is stability — equal elements can be reordered — because the long jumps of sift-down disrupt adjacency. For workloads that need stability, such as the multi-key sorts that power the Australian Taxation Office's records or the chronological merges done by the ABC's archive systems, a stable alternative is required.
On modern hardware, heapsort loses ground to quicksort because of cache behaviour. Quicksort scans contiguous partitions, which hardware prefetchers love; heapsort makes long, irregular jumps from a node to its children, which leaves the prefetcher cold and stalls the pipeline. This is why the standard-library sort in most languages is introsort, a quicksort that falls back to heapsort only when recursion goes deep enough to risk stack overflow. Even so, for embedded firmware in agricultural drones flying over the wheatbelt, or for any constrained environment without a generous stack budget, heapsort remains a clean, predictable choice.
When to reach for heapsort in real codebases
- Sorting very large files where auxiliary memory is constrained, such as log processing on regional NBN-linked edge nodes.
- Real-time schedulers where worst-case latency must be bounded and predictable.
- Embedded firmware on resource-limited microcontrollers, including those inside marine sensors deployed along the Great Barrier Reef.
- Teaching contexts where the goal is to illustrate the array-as-tree trick rather than raw throughput.
Common pitfalls when implementing heapsort
- Forgetting to shrink the heap bound on each swap, causing the algorithm to overwrite already-sorted elements.
- Using sift-up for the build phase and accepting the O(n log n) cost instead of the linear bottom-up method.
- Conflating one-based and zero-based index arithmetic, which silently produces off-by-one errors.
- Assuming stability when equal keys are present, since the algorithm gives no ordering guarantee among equals.
- Reaching for heapsort when the data is already nearly sorted, where insertion sort or timsort would beat it by an order of magnitude.
For developers honing their algorithmic instincts before a coding interview or a competitive programming round, drilling heapsort alongside the other classic sorts builds a solid mental model. The problem-solving track at hello ML offers structured practice problems that pair well with the theory covered here, and revisiting heapsort a few months after first learning it tends to reveal subtleties that the initial pass missed.