THE FOLD / LOOT / THE INVENTORY / THE HEAP
THE HEAP
the partial order that always knows the smallest
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The binary heap. A priority queue that always hands you the smallest thing first, cheaply. It is a complete binary tree with one rule — every parent is ≤ both its children — and it lives in a plain array: the children of position i sit at 2i+1 and 2i+2, no pointers needed.
The minimum is therefore always at the root, free to read. Insert a value and let it sift up past larger parents; remove the min and drop the last leaf into the root and let it sift down — both O(log n). Heapsort just extracts the min over and over: an in-place, O(n log n) worst-case sort with no recursion and no extra memory.
LIT verified live: over 20,000 random arrays the build produces a valid heap (every parent ≤ its children) and heapsort’s output exactly equals the sorted array (window.__heap.validHeap && sortEqualsSorted). [5,2,8,1,9,3] → [1,2,3,5,8,9]. FIG no framing; the parent≤child invariant, the array index rule, and the sort are exact.
The minimum is therefore always at the root, free to read. Insert a value and let it sift up past larger parents; remove the min and drop the last leaf into the root and let it sift down — both O(log n). Heapsort just extracts the min over and over: an in-place, O(n log n) worst-case sort with no recursion and no extra memory.
LIT verified live: over 20,000 random arrays the build produces a valid heap (every parent ≤ its children) and heapsort’s output exactly equals the sorted array (window.__heap.validHeap && sortEqualsSorted). [5,2,8,1,9,3] → [1,2,3,5,8,9]. FIG no framing; the parent≤child invariant, the array index rule, and the sort are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE INVENTORY, beside THE SORT and THE SKIP LIST — the loot domain of keeping your haul ordered and instantly reachable. A heap is the inventory that always surfaces the top item first. AVAN (AI) built the instrument: the sift-up, the sift-down, the extract loop, the heap check.
The weave: David names the seat (the always-ready top item); I make the tree breathe and the invariant checkable — the array-as-tree in 1D, insert and extract in 2D, the sift path in 3D. The sphere is the seam. Credit: J. W. J. Williams (heap & heapsort, 1964); R. W. Floyd (O(n) build, 1964).
The weave: David names the seat (the always-ready top item); I make the tree breathe and the invariant checkable — the array-as-tree in 1D, insert and extract in 2D, the sift path in 3D. The sphere is the seam. Credit: J. W. J. Williams (heap & heapsort, 1964); R. W. Floyd (O(n) build, 1964).
3 ONE DIMENSION
The heap is just an array. Position i’s children are at 2i+1 and 2i+2 — the tree is implicit, drawn by arithmetic, not pointers. Every parent sits below its children in value; the smallest floats to index 0.
4 TWO DIMENSIONS · INTERACTIVE
Insert a value and watch it sift up to its place; extract-min and watch the last leaf drop in and sift down. The root is always the minimum. Heapsort extracts them all in order — a sorted array falls out.
5 THREE DIMENSIONS + AVAN’S INVERSE
The heap as a turning pyramid — green, each level holding values no smaller than the level above.
AVAN’s addition (the inverse-companion): the magenta path is an element sifting to its place, swapping only with a parent or child. A fully sorted array is a total order — everything ranked against everything, expensive to maintain. A heap is the inverse bargain: keep only a partial order, parent above child, and nothing else — yet that thin skeleton is enough to always know the extreme for free. You do not sort to find the smallest; you maintain the least structure that keeps the smallest on top. The green is the loose hierarchy; the magenta is one value finding its rung without ever touching the rest.
LIT Genuine binary heap and heapsort (J. W. J. Williams, 1964; Floyd's O(n) build, 1964). Verified live: over 20,000 random arrays the build produces a valid min-heap (every parent <= its children) and heapsort's output exactly equals the sorted array (window.__heap.validHeap && sortEqualsSorted, both true). [5,2,8,1,9,3] -> [1,2,3,5,8,9]. The array index rule and the sift-up/sift-down invariants are exact.
FIG No metaphor is doing the work: the parent<=child invariant, the implicit array-tree indexing, and the heapsort output are all real and checked. A heap is a partial order (not fully sorted) that still answers 'minimum' in O(1) — shown, not asserted.
FIG No metaphor is doing the work: the parent<=child invariant, the implicit array-tree indexing, and the heapsort output are all real and checked. A heap is a partial order (not fully sorted) that still answers 'minimum' in O(1) — shown, not asserted.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE INVENTORY · David Lee Wise (ROOT0), with AVAN