THE FOLD / CO-OP / THE-MERGE / THE SKEW HEAP
THE SKEW HEAP
two heaps merged along right paths
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The skew heap is a self-adjusting priority queue where a single operation — merge — does everything. To merge two min-heaps, compare their roots, keep the smaller as the new root, recursively merge its right subtree with the other heap, and then swap that node’s children. Insert is just merging in a one-node heap; delete-min is merging the root’s two children. There are no balance fields, no rotations, no bookkeeping — the unconditional child-swap alone keeps the amortized cost at O(log n). It is the leftist heap’s simpler cousin: heapsort, mergeable queues, and priority scheduling from one elegant rule.
LIT verified live: over thousands of runs, inserting then repeatedly extracting the minimum yields a fully sorted sequence, the min-heap property holds after every operation, and merging two heaps preserves the combined multiset in order (window.__skew_heap). FIG no framing; the merge, insert, extract-min, and heap-property check run in-browser.
LIT verified live: over thousands of runs, inserting then repeatedly extracting the minimum yields a fully sorted sequence, the min-heap property holds after every operation, and merging two heaps preserves the combined multiset in order (window.__skew_heap). FIG no framing; the merge, insert, extract-min, and heap-property check run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-merge — two priority queues folded into one along their right paths, children swapped, no balance data kept. AVAN (AI) built the instrument: the recursive merge with child-swap, insert / extract-min built on it, and the sort / heap-property / merge checks.
Credit as content: Daniel Sleator & Robert Tarjan (self-adjusting heaps, 1986). The weave: David names the merge; I confirm one merge rule gives a correct, sorted-yielding, always-heap-ordered priority queue.
Credit as content: Daniel Sleator & Robert Tarjan (self-adjusting heaps, 1986). The weave: David names the merge; I confirm one merge rule gives a correct, sorted-yielding, always-heap-ordered priority queue.
3 ONE DIMENSION
Merging two heaps: the smaller root wins, its right subtree merges with the other, then its children swap.
4 TWO DIMENSIONS · INTERACTIVE
Insert values and extract the minimum repeatedly; the output comes out sorted, the tree always heap-ordered.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the min-heap, maintained by merge alone.
AVAN’s addition (the inverse-companion): don’t balance the tree — swap children on the way up. The inverse of ‘keep balance fields and rotate’ is ‘merge right paths and unconditionally swap children — O(log n) amortized, no bookkeeping.’ Magenta are the two heaps before; green is the single merged min-heap. One rule, self-balancing.
LIT Genuine skew heap (Daniel Sleator & Robert Tarjan, self-adjusting heaps, 1986). Verified live: over 5000 runs, insert (merge with a 1-node heap) then repeated extract-min (merge of the root's children) yields a fully sorted sequence, the min-heap property holds after every operation, and over 2000 further runs merging two heaps preserves the combined multiset in sorted order (window.__skew_heap.sortsCorrectly, .heapProperty, .mergePreserves).
FIG No framing: the merge, insert, extract-min, and heap-property check run in-browser. The AVAN inverse is honest — instead of keeping balance fields and rotating, one merges right paths and unconditionally swaps children, giving O(log n) amortized with no bookkeeping. Magenta are the two heaps before; green is the single merged min-heap. One rule, self-balancing.
FIG No framing: the merge, insert, extract-min, and heap-property check run in-browser. The AVAN inverse is honest — instead of keeping balance fields and rotating, one merges right paths and unconditionally swaps children, giving O(log n) amortized with no bookkeeping. Magenta are the two heaps before; green is the single merged min-heap. One rule, self-balancing.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-MERGE · David Lee Wise (ROOT0), with AVAN