Skew Heap¶
A self-adjusting meldable min-heap that joins heap-ordered binary trees along their right paths and swaps merge-path children without stored balance ranks.
Core Idea¶
A skew heap is a meldable min-heap made from a heap-ordered binary tree. Its root holds a minimum. To combine two heaps, it merges their right paths and swaps the left and right children of each merge-path node except the lowest. It does this without storing a leftist balance rank.[^ref-1e8470fa4a21]
Scope of Application¶
Sleator and Tarjan specify top-down and bottom-up ways to perform this meld. Both work on disjoint heap instances with ordered keys; insertion can meld a one-item heap, and delete-min can meld the removed root's subtrees. Their proved time bounds are amortized over operation sequences, not guarantees that every call is short.[^ref-1e8470fa4a21]
The original bottom-up delete-min must not be generalized to arbitrary duplicate keys. Jones's original publisher abstract reports that it can discard items in that setting. The corrective versions' details are outside the inspected source base.[^ref-edd5bb562b59]
Clarity¶
Ask whether the object has a root minimum, whether it melds two right paths, and whether it exchanges children without consulting a stored rank. Those answers distinguish it from a generic priority-queue interface and from a leftist heap, whose exchange is tied to a maintained rank.[^ref-1e8470fa4a21]
Manages Complexity¶
The structure avoids maintaining a separate balance rank. That simplifies its meld rule, while the original analysis permits an occasional linear-time operation. The top-down construction has logarithmic amortized insert, delete-min and meld; the bottom-up theorem gives constant amortized insert and meld and logarithmic amortized delete-min under its original assumptions.[^ref-1e8470fa4a21]
Abstract Reasoning¶
The maintained object, rather than one call to meld, is a Data Structure. It arranges keyed items in a pointer tree, keeps heap order, privileges root-minimum access and composes two heaps by melding them. Its operation profile depends on this arrangement. The sole strict parent edge is child to Data Structure by subsumption/kind_of; arrays and tables can be data structures without being skew heaps. The live generic Heap entry's array/completeness/sift signature does not cover this pointer-linked right-path design.[^ref-1e8470fa4a21]
Knowledge Transfer¶
The useful comparison is between an explicit shape constraint and a self-adjusting update rule. A skew heap uses the second and is analyzed by the sequence of operations. Transfer that question to other structures without transferring the skew heap's exact proof or duplicate-key assumptions.[ref-1e8470fa4a21][ref-edd5bb562b59]
Example¶
Top-down original construction: two disjoint heap-ordered trees are the inputs. The meld walks downward along their right paths, combines path nodes in key order, and swaps children except at the lowest node without using a balance rank. Singleton meld implements insert; subtree meld implements delete-min. Theorem 1 gives logarithmic amortized insert, delete-min and meld, with constant-time make-heap and find-min. This is a formal construction, not a measured deployment.[^ref-1e8470fa4a21]
Bottom-up original construction: two disjoint heap-ordered trees again supply the inputs. The meld walks upward along right paths and assembles the merged path with root reattachment; it uses the same rank-free exchange exception. Theorem 2 gives constant amortized insert and meld and logarithmic amortized delete-min in the original domain. This traversal and cost profile differ from top-down. Keep the distinct-key limit because Jones reports a duplicate-key delete-min failure in the published bottom-up procedure.[ref-1e8470fa4a21][ref-edd5bb562b59]
Relationships to Other Abstractions¶
Current abstraction Skew Heap Domain-specific
Parents (1) — more general patterns this builds on
-
Skew Heap is a kind of Data Structure Prime
A skew heap is a maintained arrangement of keyed items with heap order, root-minimum access and composable meld operations.
Hierarchy path (1) — routes to 1 parentless root
- Skew Heap → Data Structure → Trade-offs → Constraint
Neighborhood in Abstraction Space¶
Skew Heap sits in a sparse region of the domain-specific corpus (90th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Heap — 0.81
- B-Tree — 0.81
- Radix tree — 0.80
- Tree (Data Structure) — 0.79
- Queap — 0.79
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
A complete-array binary heap maintains a different layout and updates by sifting. A leftist heap stores a rank and swaps conditionally. A bare priority queue says what operations are wanted but not how this tree melds. Also, neither the top-down logarithmic nor bottom-up constant amortized bounds are per-operation worst-case promises, and the lowest merge-path node is exempt from exchange.[^ref-1e8470fa4a21]
References¶
[^ref-1e8470fa4a21]: Sleator, Daniel D., and Robert E. Tarjan (1986). Self-Adjusting Heaps. SIAM Journal on Computing 15(1), 52–69. DOI: 10.1137/0215004. Original full article, especially §§2–3, Figs. 1 and 5, Theorems 1 and 2, printed pp.53–63.
[^ref-edd5bb562b59]: Jones, Douglas W. (1987). A Note on Bottom-Up Skew Heaps. SIAM Journal on Computing 16(1), 108–110. DOI: 10.1137/0216009. Publisher abstract only supports the duplicate-key limitation; no full-text correction procedure is claimed.