THE BINARY HEAP the frontier the darts named, on the array
A complete binary tree flattened into an array — node i’s children are 2i+1 and 2i+2, no pointers — that always keeps its smallest (or largest) at the top. It is the priority queue that Dijkstra (dart 055) and A* (dart 052) said they wanted; and it turns out to run on I-13’s existing array today, no new value kind required.
THE TECHNIQUE sift down until the shape is restored
Store the tree in an array by rows. To fix a node, compare it with its two children and swap with the larger (max-heap); repeat down the tree — a sift-down. Build a heap by sifting every internal node bottom-up (linear time), then heapsort: swap the top to the end, shrink, sift the new top down. Watch it sort. live demo
HISTORY & CREDIT one 1964 page, two names
Taught as if it were always here — it arrived in a single textbook chapter half-page algorithm listing in 1964. cited
1964 · J. W. J. Williams publishes “Algorithm 232: Heapsort” (CACM) — introducing the heap data structure AND the sort that uses it, in one go. 1964 · Robert W. Floyd (“Algorithm 245: Treesort 3”) gives the bottom-up build-heap in O(n) — faster than n inserts — and the cleaner sift-down. the array trick · a complete tree needs no pointers: children live at 2i+1, 2i+2, the parent at (i−1)/2. The structure is pure index arithmetic on a flat array. the family · a binary heap gives O(log n) insert / extract; the Fibonacci heap (Fredman-Tarjan, 1984) gives O(1) amortised decrease-key — the version fast Dijkstra cites.
Every priority queue, every event simulation, every A* frontier is a heap underneath. the quiet workhorse
RECOMMEND FOR I-13 PS-005 closes — the heap runs on the array
The heap is an array plus index arithmetic and swaps, all of which I-13 has. Heapsort runs on the real compiler (build a max-heap by sifting, then sort in place):
$ i13 run heap.i13 # sift-down heap embedded in a bounded array
sorted[0] = 1 sorted[3] = 4 sorted[7] = 10 # [4,10,3,5,1,8,2,7] -> ascending
Recommend:closes PS-005. Darts 052 (A*) and 055 (Dijkstra) named a binary heap as their open want — and here it is, running on the bounded array today, no new value kind. Their “wanted a heap” was really “we used a linear scan”; the heap itself was always expressible (2i+1 / 2i+2 index arithmetic + array swaps). The one friction: a priority-queue extract-min naturally returns (min, reduced-heap) — two values — so it nudges the same multiple-return frontier (do it as peek-then-sift and it runs, just less tidily). The structure is landed; only the ergonomics wait on the pair.