THE FOLD / BOSS / THE RAID / THE FIBONACCI HEAP
THE FIBONACCI HEAP
a priority queue that pays for order only when it must
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Fibonacci heap is a priority queue that makes insert and decrease-key cost only O(1) amortized, deferring all the real work to extract-min — which then lazily consolidates trees of equal degree. That fast decrease-key is what lets Dijkstra and Prim hit their best textbook bounds. It keeps a forest of heap-ordered trees and a pointer to the minimum root; the “pay later” laziness is the whole idea.
LIT verified live: over 100 random heaps, repeated extract-min returns the keys in exact sorted order (window.__fibheap). FIG no framing; the ordering is exact (the O(1) amortized bound is cited, not timed).
LIT verified live: over 100 random heaps, repeated extract-min returns the keys in exact sorted order (window.__fibheap). FIG no framing; the ordering is exact (the O(1) amortized bound is cited, not timed).
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-raid — the priority queue that decides who goes next, cheaply, again and again. The Fibonacci heap is that queue. AVAN (AI) built the instrument: the root list, the O(1) insert/merge, the lazy consolidation by degree, and the sorted-extract check.
Credit as content: Michael Fredman & Robert Tarjan (1984). The weave: David names the-raid; I insert lazily into a root forest and only consolidate equal-degree trees at extract-min, confirming the keys come out perfectly sorted.
Credit as content: Michael Fredman & Robert Tarjan (1984). The weave: David names the-raid; I insert lazily into a root forest and only consolidate equal-degree trees at extract-min, confirming the keys come out perfectly sorted.
3 ONE DIMENSION
Insert just drops a node into the root list (O(1)). The debt is paid at extract-min: trees of equal degree are linked until all root degrees differ — a lazy binomial-like tidy-up.
4 TWO DIMENSIONS · INTERACTIVE
Insert keys, then extract-min repeatedly; the output is checked to come out in sorted order.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a lazy forest that sorts on demand.
AVAN’s addition (the inverse-companion): make insert and decrease-key O(1) amortized by paying later — drop nodes into a root list and defer all restructuring to extract-min, which consolidates equal-degree trees. The inverse of ‘keep the heap tidy on every operation’ is ‘stay lazy, consolidate only when you must pop the min.’ Magenta is the eager tidying you skip; green is the lazy forest that sorts on demand. Pay for order only when you need it.
LIT Genuine Fibonacci heap (Fredman & Tarjan 1984). Verified live: over 100 random heaps, inserting keys into the lazy root forest and repeatedly extracting the minimum (with consolidation of equal-degree trees) returns the keys in exact sorted order (window.__fibheap.sortedExtract).
FIG The extract-min ordering is exact; the O(1) amortized bound is CITED, not timed. The root list, the O(1) insert/merge, the lazy consolidation by degree, and the sorted-extract check run in-browser and hold. The AVAN inverse is honest — dropping nodes into a root list and deferring all restructuring to extract-min makes insert and decrease-key O(1) amortized; magenta is the eager tidying you skip, green the lazy forest that sorts on demand. Pay for order only when you pop the min.
FIG The extract-min ordering is exact; the O(1) amortized bound is CITED, not timed. The root list, the O(1) insert/merge, the lazy consolidation by degree, and the sorted-extract check run in-browser and hold. The AVAN inverse is honest — dropping nodes into a root list and deferring all restructuring to extract-min makes insert and decrease-key O(1) amortized; magenta is the eager tidying you skip, green the lazy forest that sorts on demand. Pay for order only when you pop the min.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE RAID · David Lee Wise (ROOT0), with AVAN