Heap sort: a tree inside an array
Heap sort builds a max-heap, moves its largest element to the end, then restores the heap in the remaining prefix. The tree and array below are two views of the same elements.
Up to 15 values; empty input is allowed. Letters distinguish equal values.
Step 0 / 102: Build a max-heap from the last parent upwards.
Build heap · Heap: [0, 10) · Sorted suffix: [10, 10)
Array: [8, 3a, 6a, 2, 5, 3b, 9, 1, 6b, 4]
Comparisons: 0 · Swaps: 0
Tree and array show the same items. Yellow: compared positions; cyan: chosen child; outline: parent. Green: final positions, with a line at the start of the sorted suffix. Indices start at zero. Long values are abbreviated on canvas; full values appear above.
Video walkthrough
A heap is not a fully sorted tree
A binary heap is a complete binary tree: levels fill from left to right. In a max-heap, each parent is at least as large as its children. This puts the maximum at the root, but does not order siblings or separate subtrees.
No linked nodes are needed. In a zero-based array, index i has children at 2i + 1 and 2i + 2, provided they are below heapSize. Its parent is floor((i − 1) / 2). The active heap occupies [0, heapSize); the sorted suffix occupies [heapSize, n).
Build from the bottom
Leaves already satisfy the heap property. Start at floor(n / 2) − 1, the last parent, and sift each parent down towards index zero. When a parent is processed, both of its child subtrees are already heaps.
Sift-down chooses the larger child; ties go to the left. If that child is greater than the parent, exchange them and continue from the child's position. Otherwise stop. For [1, 3, 2], construction exchanges 1 and 3, producing [3, 1, 2].
Extract and restore
Exchange the root with the last active element, then decrease heapSize. The extracted maximum is now in its final position. Only the new root can violate the heap property, so sift it down to restore the heap.
For [3, 1, 2], extraction gives [2, 1 | 3]. The prefix is already a heap. The next extraction gives [1 | 2, 3], and the final singleton completes the result. Green cells never move again; their tree nodes disappear when the active size decreases.
During sift-down the heap property can temporarily fail along the active path. After restoration, the prefix is a max-heap, the suffix is sorted, and every prefix value is no greater than any suffix value. The comparison counter counts value comparisons between children and between parent and chosen child. The swap counter includes both sift-down and extraction exchanges. Index checks are not counted.
Why it is not stable
Letters track original identities; they do not affect comparisons. Try the Instability preset: [2a, 2b, 1]. The heap needs no initial exchanges. Extraction moves 2a to the end; restoration then exchanges 1 and 2b. The result is [1, 2b, 2a]. Equal values have reversed their original order.
Choosing the left child on ties does not make this algorithm stable. Long-distance extraction exchanges can still reorder equal elements.
Time and space
Bottom-up heap construction takes O(n): most nodes are near the leaves and travel only a short distance. Summing work across levels gives a linear bound rather than multiplying every node by the tree height.
Sorting takes O(n log n) in the worst case. Each extraction can sift through O(log n) levels. This implementation stops sifting early: on all-equal input it performs linear work, so not every input takes Θ(n log n).
The iterative in-place algorithm uses O(1) auxiliary memory. The code below copies the input and therefore uses O(n) additional space. The interactive player also retains snapshots for seeking; these can require O(n² log n) space. Its 15-element limit is a visualization constraint.
function heapSort(input) {
const a = [...input];
if (a.some(value => !Number.isFinite(value))) {
throw new TypeError("Expected finite numbers");
}
function siftDown(root, size) {
while (2 * root + 1 < size) {
let child = 2 * root + 1;
const right = child + 1;
if (right < size && a[right] > a[child]) child = right;
if (a[child] <= a[root]) break;
[a[root], a[child]] = [a[child], a[root]];
root = child;
}
}
for (let root = Math.floor(a.length / 2) - 1; root >= 0; root--) {
siftDown(root, a.length);
}
for (let end = a.length - 1; end > 0; end--) {
[a[0], a[end]] = [a[end], a[0]];
siftDown(0, end);
}
return a;
}Choosing between sorts
Heap sort offers a worst-case O(n log n) bound with constant auxiliary space when used in place. Merge sort can preserve equal-value order but usually needs a buffer for arrays. Quick sort often performs well in practice, while its worst case depends on pivot choices and partitioning. Choose according to stability, memory and workload requirements.