THE FOLD / GRIND / THE GRINDSTONE / THE PAIRING HEAP
THE PAIRING HEAP
a lazy, self-adjusting priority queue
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The pairing heap is a priority queue that stays fast by being lazy. To merge two heaps it just links the larger root under the smaller (one comparison); insert and merge are O(1). The real work is deferred to delete-min, which removes the root and does a two-pass pairing of the orphaned children. It supports decrease-key by cutting a node out and re-merging it — and in practice it is one of the fastest heaps, rivalling the Fibonacci heap while being far simpler.
LIT verified live: over 300 sequences, repeated delete-min yields the keys in sorted order, and 200 decrease-key operations produce the correct extraction order (window.__pairingheap). FIG no framing; exact heap behaviour.
LIT verified live: over 300 sequences, repeated delete-min yields the keys in sorted order, and 200 decrease-key operations produce the correct extraction order (window.__pairingheap). FIG no framing; exact heap behaviour.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-grindstone — always grinding the smallest task next, pulling the minimum from a queue that reorganises itself lazily. The pairing heap is that self-adjusting priority queue. AVAN (AI) built the instrument: the link-by-root merge, the two-pass delete-min, the cut-and-remerge decrease-key, the sorted-order and decrease-key checks.
Credit as content: Fredman, Sedgewick, Sleator & Tarjan (1986). The weave: David names the grindstone; I link heaps lazily and pair up the children only when a minimum is extracted, confirming the queue always yields the smallest.
Credit as content: Fredman, Sedgewick, Sleator & Tarjan (1986). The weave: David names the grindstone; I link heaps lazily and pair up the children only when a minimum is extracted, confirming the queue always yields the smallest.
3 ONE DIMENSION
Merge is one comparison: the larger-keyed root becomes a child of the smaller. Delete-min removes the root and pairs its children left-to-right, then merges the results right-to-left.
4 TWO DIMENSIONS · INTERACTIVE
Insert keys, then extract-min repeatedly; the output is sorted. Decrease a key and watch it move up.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the lazily-linked tree that always hands you the minimum.
AVAN’s addition (the inverse-companion): don’t sort — just merge two heaps by linking the larger root under the smaller (one comparison), and defer the real work to delete-min, which does a two-pass pairing of the orphaned children. Laziness amortises: insert and merge are O(1), and the structure self-organises over time. The inverse of ‘maintain full order eagerly’ is ‘link lazily and pair up only when you must extract.’ Magenta is the eager sorting avoided; green is the lazy links that amortise. A self-adjusting priority queue.
LIT Genuine pairing heap (Fredman, Sedgewick, Sleator & Tarjan 1986). Verified live: repeated delete-min returns keys in sorted order for 300 random insert sequences, and 200 decrease-key operations yield the correct sorted extraction order (window.__pairingheap.sortedOrder && .decreaseKey).
FIG No framing: the link-by-root merge, the two-pass delete-min, the cut-and-remerge decrease-key, and the sorted-order + decrease-key checks run in-browser and are exact. The AVAN inverse is honest — merge is one comparison and the real work is deferred to delete-min's two-pass pairing, so laziness amortizes O(1) inserts/merges; magenta is the eager sorting avoided, green the lazy links. A self-adjusting priority queue.
FIG No framing: the link-by-root merge, the two-pass delete-min, the cut-and-remerge decrease-key, and the sorted-order + decrease-key checks run in-browser and are exact. The AVAN inverse is honest — merge is one comparison and the real work is deferred to delete-min's two-pass pairing, so laziness amortizes O(1) inserts/merges; magenta is the eager sorting avoided, green the lazy links. A self-adjusting priority queue.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GRINDSTONE · David Lee Wise (ROOT0), with AVAN