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 self-adjusting, meldable min-heap specified by Sleator and Tarjan. Its items occupy a heap-ordered binary tree: each parent's key is no greater than its children's, so the root holds a minimum. The fundamental update melds two disjoint heaps by recombining their right paths. The method exchanges the left and right children of each merge-path node except the lowest and stores no leftist balance rank.[1]
The original paper gives top-down and bottom-up constructions. They share this structure and update rule while traversing and assembling the merged path differently. They also have different amortized operation bounds. Neither construction promises logarithmic time for each individual operation.[1]
Structural Signature¶
- Keyed, heap-ordered carrier: A rooted pointer-linked binary tree holds ordered items and exposes a minimum at its root. Remove heap order and the root-minimum contract disappears.[1]
- Meld inputs: Two disjoint heap instances enter a destructive merge. Insertion melds a singleton; deletion of the minimum melds the removed root's two subtrees. Without this composable merge, the distinctive update contract is absent.[1]
- Right-path recombination: The two right paths are merged in key order. Top-down and bottom-up procedures differ in traversal and assembly, but both use those paths.[1]
- Rank-free local exchange: Children are exchanged at each merge-path node other than the lowest, without consulting a stored balance rank. Replace this with a rank-conditioned leftist swap and the named skew adjustment is lost.[1]
- Operational contract: Make-heap, find-min, insert, delete-min and meld remain meaningful operations on the maintained min-heap. Their bounds must be read as construction-specific and amortized where the original theorems say so.[1]
What It Is Not¶
A bare priority-queue interface does not specify a skew heap's tree or meld rule. A complete-array binary heap sifts nodes within an implicit tree rather than melding right paths. A leftist heap is a closer near miss: it also melds heap-ordered trees, but maintains shortest-path rank and conditionally exchanges children to preserve a leftist constraint. Skew heaps omit that rank test.[1]
Nor is the bottom-up construction an unconditional duplicate-key algorithm. Jones's original publisher abstract reports that the published bottom-up delete-min can drop items when duplicate keys occur. This entry describes the original distinct-key baseline and does not infer the details of later corrections from that abstract.[2]
Scope of Application¶
The two positive constructions are formal operations on disjoint heap instances with ordered keys, not reports of two field deployments. The original top-down account gives constant-time make-heap and find-min and logarithmic amortized insert, delete-min and meld. Its worst-case discussion shows that an individual operation can take linear time. The bottom-up theorem gives constant-time amortized make-heap, find-min, insert and meld, and logarithmic amortized delete-min under its stated representation and key assumptions.[1]
No application workload, empirical speed ranking, universal pointer count, arbitrary tie policy, or corrected duplicate-key algorithm is established by the inspected sources. A use that needs a guaranteed small latency for every operation must test the actual implementation and requirement instead of reading the amortized bound as a worst-case guarantee.[1][2]
Clarity¶
To recognize the object, ask where the minimum sits, what two trees meld, which paths are recombined, and what directs each child exchange. “At the root,” “two heap-ordered trees,” “their right paths,” and “an exchange without a stored rank except at the lowest path node” identify the skew-heap mechanism. The answers also separate it from array and leftist heaps.[1]
Manages Complexity¶
The original design avoids maintaining a separate leftist balance rank while retaining a simple merge-centered account of insertion and deletion. It buys that simplicity with an amortized guarantee over sequences rather than a low bound on every single call. This matters when many updates are evaluated together, but it does not erase occasional costly operations.[1]
Abstract Reasoning¶
The transferable reasoning step is to analyze a maintained representation through its invariant and update sequence. Both original procedures preserve heap order and use the same rank-free right-path exchange. Their different traversal direction changes the analysis: top-down meld is logarithmic amortized; bottom-up meld is constant amortized in the original theorem's domain. The distinction is about the specified construction and assumptions, not a license to assign bottom-up bounds to every skew-heap implementation.[1]
Knowledge Transfer¶
The skew heap illustrates how a local self-adjustment can replace an explicit shape constraint while preserving a useful sequence-level cost. That comparison can guide analysis of other self-adjusting structures, but the exact right-path operation, ordered-key assumptions and theorems stay attached to skew heaps. Moving only the slogan “swap children” into another structure would not transfer the proof.[1]
Examples¶
Top-down original construction. Two disjoint heap-ordered binary trees supply the keyed carriers and meld inputs. Their right paths are traversed downward and merged in increasing-key order. Children are exchanged on every merge-path node except the lowest, with no leftist rank. Meld then supports singleton insertion and root-subtree delete-min. Theorem 1 gives logarithmic amortized insert, delete-min and meld, while make-heap/find-min are constant time. This is a complete formal case, not an observed workload or a worst-case-per-call result.[1]
Bottom-up original construction. The same heap-ordered carrier and disjoint meld inputs remain. The procedure walks upward along the right paths, assembles the merged path and reattaches the root as in the original Fig. 5; it makes the same rank-free exchanges except at the lowest node. Theorem 2 gives constant amortized insert and meld and logarithmic amortized delete-min under the paper's original setup. Its traversal, assembly and operation profile differ from the top-down case. Jones's abstract limits the published bottom-up procedure when duplicate keys are allowed, so this positive case retains the distinct-key baseline.[1][2]
Structural Tensions¶
Avoiding maintained balance metadata simplifies the update rule, but it gives up a strong latency bound for every individual operation. Sleator and Tarjan prove useful amortized bounds yet exhibit a linear-time individual operation. The practical diagnostic is: can the intended workload tolerate occasional expensive calls in return for this rank-free, meld-centered structure? The answer depends on the workload and implementation; the original paper does not report a universal empirical winner.[1]
Structural–Framed Character¶
Skew heap lies toward the structural end of the structural–framed spectrum. Its recognition conditions are formal: heap order, right-path meld, exchange except at the lowest node, and no stored rank are the same tests in both original constructions. Its name came from a particular computer-science design and paper, but historical origin alone does not define its present instances. Human practice enters when an implementer chooses between the two procedures or evaluates latency tolerance; that choice changes variant and use, not the shared identity. Evaluative weight belongs to amortized versus per-operation performance, not to whether the object is a skew heap. A different implementation can be recognized by the mechanism without importing the original paper's workload, pointer representation, or bottom-up complexity theorem. Its character: a formal, structurally recognized data structure with construction-specific analyses, rather than a context-governed label.[1]
Structural Core vs. Domain Accent¶
The core is the heap-ordered pointer tree, disjoint-heap meld, right-path recombination, rank-free exchange except at the lowest node, and meld-derived min-heap operation contract. Top-down versus bottom-up traversal, exact pointer representation and the corresponding amortized theorem are accents. The live Prime Data Structure supplies the broader skeleton: keyed information, chosen layout, maintained invariant, operation profile, design tradeoff and composability. Skew heap adds ordered binary-tree pointers and its exact meld-path rule.[1]
That extra rule blocks a Prime promotion. A general data structure can be an array, table or index and need not meld heaps at all; transplanting only “self-adjustment” or “priority access” would not recreate a skew heap. A possible future cross-domain abstraction about rank-free self-adjustment would require independent unlike instances and its own evidence. It is not asserted by these two variants of one data-structure family.
Instantiates / Related Primes¶
This entry is a kind of Data Structure.
A skew heap is, in every case, a kind of Data Structure, its one broader abstraction. Keyed items are arranged in a pointer tree, heap order is maintained, root minimum and meld/update are privileged operations, and melding composes two instances. The choice sacrifices a worst-case low latency guarantee for a rank-free amortized design. These fill all of Data Structure's roles in both original cases. Other data structures lack this specific right-path rule, so the skew heap is narrower.[1]
It is tempting to call it a kind of Heap, but under Heap's present full definition it is not one: it requires an implicit contiguous-array complete tree and sift updates, which the skew heap does not have. Algorithm is also not a broader kind for the whole maintained object; meld is one of its procedures. No second broader abstraction is claimed from shared terminology alone.
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.Ordered items are stored in a pointer-linked binary tree; heap order is its maintained invariant. The root privileges minimum access, and melding two disjoint instances composes their arrangements. Rank-free right-path exchange gives amortized update bounds but permits expensive individual operations, making the layout's operation profile consequential rather than neutral. Other data structures use arrays, tables or indexes without skew-heap meld, so this is strict subsumption rather than identity.
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¶
Do not confuse an amortized logarithmic top-down operation with a worst-case logarithmic call, or a constant amortized bottom-up meld with a constant worst-case meld. Do not infer duplicate-key safety for the original bottom-up delete-min; Jones reports the contrary. The lowest merge-path node is not exchanged in either original construction. None of these corrections changes the shared heap-ordered, rank-free, right-path identity.[1][2]
References¶
[1] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u
[2] 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. registry ↩a ↩b ↩c ↩d