THE HEAPSORT a tree in an array — O(n log n) worst case, in place, no recursion needed
Heapsort gets guaranteed O(n log n) with no extra memory by building a binary heap inside the array itself — parent at i, children at 2i+1 and 2i+2, no pointers. First it heapifies (sift-down from the middle so every parent dominates its children, putting the maximum at the root); then it repeatedly swaps the root to the end and re-sifts. It has quicksort’s speed with a hard worst-case guarantee, and its heap doubles as a priority queue. The engine is sift-down; here it builds the max-heap and the root becomes the maximum.
THE TECHNIQUE heap in an array (children 2i+1,2i+2); sift-down; root = max
The demo builds a max-heap of [4,10,3,5,1] by sift-down — the root becomes the maximum, 10: live demo
HISTORY & CREDIT J.W.J. Williams · 1964
“A tree needs pointers.” — a binary heap lives in a flat array by index arithmetic; no pointers at all. cited
the layout · parent i, children 2i+1, 2i+2 — a complete tree in an array. heapify · sift-down from the middle so each parent dominates — the max reaches the root. 1964 · J.W.J. Williams — the heap and heapsort; O(n log n) worst case, in place.
A tree folded into an array by index alone, its maximum lifted to the root — sorting with a guarantee. resource
RECOMMEND FOR I-13 the built heap, on the compiler
On the canonical compiler, building a max-heap of [4,10,3,5,1] puts the maximum, 10, at the root:
$ i13 run or_heapsort.i13 # build max-heap by sift-down
RUN OK · 296 step(s) · peak stack 6 · call depth 5
root_is_max = 1 -- heap[0] == 10 after heapify
Recommend as a NULL — resource, the guaranteed kind. Heapsort produces the same sorted output with a worst-case O(n log n) guarantee and no extra memory (B40) — the tree-in-an-array is a clever encoding (B44) of a complete tree by index. No new invariant. NULL — and note the pointerless tree here is what the seated keeper Stern-Brocot did for a different structure.