THE FOLD / GRIND / THE EPOCH / THE BINOMIAL HEAP
THE BINOMIAL HEAP
a heap counted in binary
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The binomial heap is a priority queue built as a forest of binomial trees — trees of sizes 1, 2, 4, 8, …, exactly the powers of two. A heap of n elements has one tree for each 1-bit in the binary of n, so its shape is the binary numeral of its size. Merging two heaps works like binary addition: line the trees up by order and carry-link equal orders, giving O(log n) union — and insert, extract-min and decrease-key all follow. Each tree obeys the heap order, so the minimum is always a root.
LIT verified live: draining a heap by repeated extract-min returns the keys in sorted order, and merging two heaps then draining yields the combined sorted sequence (window.__binomial_heap). FIG no framing; the linking, union, and extract-min all run in-browser.
LIT verified live: draining a heap by repeated extract-min returns the keys in sorted order, and merging two heaps then draining yields the combined sorted sequence (window.__binomial_heap). FIG no framing; the linking, union, and extract-min all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-epoch — a queue that always serves the smallest key next, epoch by epoch, and merges whole queues like adding binary numbers. AVAN (AI) built the instrument: binomial linking, the carry-propagating union, and extract-min, checked against a sorted reference.
Credit as content: Jean Vuillemin (1978). The weave: David names the epoch; I confirm the heap drains in sorted order and that merging two heaps drains to the combined sorted sequence.
Credit as content: Jean Vuillemin (1978). The weave: David names the epoch; I confirm the heap drains in sorted order and that merging two heaps drains to the combined sorted sequence.
3 ONE DIMENSION
The forest for a heap of n elements: one binomial tree per 1-bit of n — its shape is the binary numeral of its size.
4 TWO DIMENSIONS · INTERACTIVE
Insert keys (watch the trees carry-link like binary addition) and extract the minimum; the drained sequence comes out sorted.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the forest of binomial trees, heap-ordered.
AVAN’s addition (the inverse-companion): don’t track the trees — read the count in binary. The inverse of ‘which trees are present?’ is ‘the 1-bits of n say exactly which orders exist, and union is binary addition with carries.’ Magenta is the current minimum root; green is the binary-counter forest. A heap counted in binary.
LIT Genuine binomial heap (Jean Vuillemin, 1978): forest of binomial trees, union by carry-linking (binary addition). Verified live: extract-min drains in sorted order (window.__binomial_heap.sortedExtraction), and merging two heaps then draining equals the combined sorted sequence (.mergeOk).
FIG No framing: the linking, the carry-propagating union, and extract-min all run in-browser, checked against a sorted reference. The AVAN inverse is honest — the 1-bits of n saying exactly which tree-orders exist (and union being binary addition with carries) is the structural identity of the heap; magenta is the minimum root, green the binary-counter forest. A heap counted in binary.
FIG No framing: the linking, the carry-propagating union, and extract-min all run in-browser, checked against a sorted reference. The AVAN inverse is honest — the 1-bits of n saying exactly which tree-orders exist (and union being binary addition with carries) is the structural identity of the heap; magenta is the minimum root, green the binary-counter forest. A heap counted in binary.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE EPOCH · David Lee Wise (ROOT0), with AVAN