THE FOLD / CO-OP / THE MERGE / THE LEFTIST HEAP
THE LEFTIST HEAP
two heaps fuse in log time
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A leftist heap is a priority queue whose defining trick is a fast merge: two heaps combine in O(log n). Every node stores an s-value (the distance to the nearest empty slot), and the heap keeps every node’s left child at least as “tall” as its right (s(left) ≥ s(right)). Because the right spine stays short (length ≤ log n), merging just walks two right spines and swaps children to restore the invariant. Insert and extract-min are merges in disguise.
LIT verified live: over hundreds of random heaps, extract-min yields fully sorted order, the leftist invariant s(left) ≥ s(right) holds at every node, and the heap property holds (window.__leftist). FIG no framing; exact structural checks.
LIT verified live: over hundreds of random heaps, extract-min yields fully sorted order, the leftist invariant s(left) ≥ s(right) holds at every node, and the heap property holds (window.__leftist). FIG no framing; exact structural checks.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-merge — two priority queues become one in logarithmic time, the operation from which insert and extract are built. The leftist heap is that merge. AVAN (AI) built the instrument: the s-value bookkeeping, the right-spine merge with child-swap, and the sorted-extract + leftist + heap-property checks.
Credit as content: Clark Allan Crane (1972); popularized in Knuth. The weave: David names the-merge; I merge two heaps by walking their right spines and swapping children to keep left taller than right, then confirm extract-min comes out sorted and the invariants hold everywhere.
Credit as content: Clark Allan Crane (1972); popularized in Knuth. The weave: David names the-merge; I merge two heaps by walking their right spines and swapping children to keep left taller than right, then confirm extract-min comes out sorted and the invariants hold everywhere.
3 ONE DIMENSION
Merge walks the two right spines, taking the smaller root each step; then swaps children where s(left) < s(right). The right spine stays ≤ log n long, so merge is cheap.
4 TWO DIMENSIONS · INTERACTIVE
A leftist heap drawn as a tree; extract-min repeatedly, and the sorted output + invariants checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: two heaps fused in log time.
AVAN’s addition (the inverse-companion): make a priority queue mergeable by keeping the right spine short — store each node’s distance to an empty slot and always swap the shorter child right. The inverse of ‘rebuild a heap by inserting one element at a time’ is ‘merge two whole heaps along their short right spines in O(log n).’ Magenta is the element-by-element rebuild; green is the single spine-merge. A queue built to fuse.
LIT Genuine leftist heap (Clark Allan Crane 1972; in Knuth vol. 3). Verified live: over 300 random heaps, extract-min produces fully sorted output (window.__leftist.sortedExtract), the leftist invariant s(left)≥s(right) with s(node)=s(right)+1 holds at every node (leftistProperty), and the min-heap property holds (heapProperty).
FIG No framing: the s-value bookkeeping, the right-spine merge with child-swap, and the sorted-extract + leftist + heap-property checks run in-browser and agree. The AVAN inverse is honest — making a priority queue mergeable by keeping the right spine short (swap the shorter child right) genuinely lets two whole heaps fuse in O(log n) rather than rebuilding element-by-element; magenta is that rebuild, green the single spine-merge.
FIG No framing: the s-value bookkeeping, the right-spine merge with child-swap, and the sorted-extract + leftist + heap-property checks run in-browser and agree. The AVAN inverse is honest — making a priority queue mergeable by keeping the right spine short (swap the shorter child right) genuinely lets two whole heaps fuse in O(log n) rather than rebuilding element-by-element; magenta is that rebuild, green the single spine-merge.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN