Skew Heap

Skew heap (or self-adjusting heap) is a mergeable priority queue data structure within computation and algorithms implemented as a heap-ordered binary tree that maintains logarithmic amortized efficiency without storing any balance information, rank, or subtree size at its nodes. Introduced by Daniel Dominic Sleator and Robert Endre Tarjan in the SIAM Journal on Computing in 1986 as the priority-queue counterpart to their self-adjusting binary search tree (the splay tree), a skew heap simplifies the leftist tree of Clark A. Crane (1972) and Donald E. Knuth (1973) by eliminating the null-path length field s(x) altogether.

Whereas a leftist tree merges two heaps along their rightmost spines and conditionally swaps the left and right children of a visited node x only when s(left(x)) < s(right(x)), a skew heap unconditionally swaps the left and right children of every node along the merge path (except the deepest node, which has no right child to merge). Although a single skew-heap tree can degenerate into a linear right spine of depth Θ(n) in the worst case, Sleator and Tarjan proved via the potential method of amortized analysis—counting the number of heavy right children whose subtree size exceeds half their parent's subtree size—that Meld, Insert, and Delete-Min each execute in O(log n) amortized time, while Find-Min runs in O(1) worst-case time. Together with the pairing heap (invented by Fredman, Sedgewick, Sleator, and Tarjan in the same year), the skew heap demonstrated that self-adjusting local restructuring can match or outperform explicitly balanced structures such as the Fibonacci heap and Brodal queue in practical pointer-based applications.

Unconditional Child Swapping Along the Right Spine

In a skew heap, each node x stores only three fields: its priority key key[x], a left child pointer left(x), and a right child pointer right(x). No parent pointer, null-path length s(x), degree, or mark bit is required. Every node obeys the standard min-heap ordering invariant: for every child y of x, key[x] ≤ key[y].

The fundamental operation is Meld(H₁, H₂), which merges two node-disjoint skew heaps H₁ and H₂ into a single skew heap:

1. Base case: If H₁ = □ (empty), return H₂; if H₂ = □, return H₁.
2. Root comparison: Compare key[H₁] and key[H₂]. If key[H₁] > key[H₂], exchange the references H₁ ↔ H₂ so that H₁ always has the smaller root key.
3. Unconditional child swap and recursive merge: Save the old right child temp ← right(H₁), move the untouched left subtree to the right by setting right(H₁) ← left(H₁), and recursively merge temp with H₂ into the new left child:

1. Return: Return H₁ as the root of the combined skew heap.

Equivalently, if one imagines interleaving the rightmost paths of H₁ and H₂ in sorted key order to form a single combined rightmost spine, Meld finishes by swapping the left and right children of every node along that merged spine (except the bottommost node). Because every old right child along the merge path is rotated over to the left subtree—and its former left sibling becomes the new right child—any long right path encountered during an expensive Meld is automatically broken up and transferred into the left subtrees for subsequent operations.

Bottom-Up vs. Top-Down Iterative Meld

Sleator and Tarjan (1986) described two non-recursive implementations of Meld:

• Bottom-up iterative Meld: Walk down the right spines of H₁ and H₂, temporarily reversing the right pointers to record the ancestor chain (pointer reversal), and then walk back up to the root while restoring pointers and swapping left and right children at each ancestor.
• Top-down iterative Meld: Maintain the tail of the new left spine of the merged heap as the algorithm descends the old right spines of H₁ and H₂. At each step, the root with the smaller key x has its old left child left(x) moved directly to right(x), while left(x) is linked as the next node on the growing left spine of the result. Top-down melding traverses the merge path only once, requires O(1) auxiliary workspace, and avoids recursion stack overhead.

All standard priority-queue operations are implemented via Meld:

• Find-Min(H): Return key[H] in O(1) worst-case time.
• Insert(H, x): Create a single-node skew heap {x} and return Meld(H, {x}) in O(log n) amortized time.
• Delete-Min(H): Delete the root of H and return Meld(left(H), right(H)) in O(log n) amortized time.

Heavy vs. Light Nodes and the Potential Function Φ(H)

Because a skew heap stores no balance state, a single Meld can visit Θ(n) nodes if previous insertions created a long right spine. To bound the amortized cost over any sequence of operations, Sleator and Tarjan classify every non-root node x (with parent p(x)) according to its subtree weight w(x), defined as the total number of nodes in the subtree rooted at x:

• Node x is heavy if its subtree contains strictly more than half of the nodes in its parent's subtree:

• Node x is light if its subtree contains at most half of the nodes in its parent's subtree:

Two structural properties follow directly from the definition of weight w(p(x)) = 1 + w(left(p(x))) + w(right(p(x))):

1. Sibling mutual exclusion: At most one of the two children of any node u can be heavy; if the right child of u is heavy, its left sibling must be light, and vice versa.
2. Logarithmic light-node bound: Along any downward path from the root of an n-node tree, each transition to a light child cuts the subtree weight w by at least a factor of 2. Therefore, any path in an n-node binary tree contains at most ⌊log₂ n⌋ light nodes.

Sleator and Tarjan define the potential function Φ(H) of a skew heap (or collection of skew heaps) as the total number of right-heavy nodes—that is, heavy nodes that are currently the right child of their parent:

Notice that Φ(∅) = 0 for an empty heap and Φ(H) ≥ 0 at all times.

Proof of O(log n) Amortized Meld

Consider melding two skew heaps H₁ and H₂ of sizes n₁ and n₂, with n = n₁ + n₂. Before the meld begins, trace the rightmost spines of H₁ and H₂:

• Let l₁ and l₂ be the number of light right children on the right spines of H₁ and H₂. By the logarithmic light-node bound, l₁ ≤ ⌊log₂ n₁⌋ and l₂ ≤ ⌊log₂ n₂⌋.
• Let h₁ and h₂ be the number of heavy right children on the right spines of H₁ and H₂.

The actual number of nodes visited during Meld(H₁, H₂) is c ≤ (l₁ + h₁ + 1) + (l₂ + h₂ + 1) = l₁ + l₂ + h₁ + h₂ + 2. Now examine how the potential Φ changes:

1. Only nodes whose subtrees gain new descendants—namely, the nodes along the merged right spine—can have their children's heavy/light status change.
2. Every node on the merge path has its left and right children swapped. Consequently, all h₁ + h₂ heavy right children along the old right spines are moved to become left children in the merged tree, and their old left siblings (which were necessarily light before the meld, by sibling mutual exclusion, and remain light afterward because all newly merged nodes are added only to the other branch) become the new right children. Thus all h₁ + h₂ right-heavy nodes along the spine are eliminated from Φ, reducing the potential by −(h₁ + h₂).
3. Meanwhile, at most the l₁ + l₂ formerly light nodes along the right spines could become right-heavy after swapping, increasing Φ by at most +(l₁ + l₂).

Therefore, the net change in potential satisfies:

Adding the actual cost c and the potential change ΔΦ cancels out the unbounded heavy terms h₁ + h₂ completely:

Cache and Instruction Efficiency vs. Leftist Trees

Although a skew heap performs an unconditional pointer swap at every node on the merge path while a leftist tree swaps only when s(left(x)) < s(right(x)), the skew heap eliminates the memory reads, arithmetic increments, and conditional branches required to maintain s(x) during bottom-up unwinding. Moreover, in top-down iterative mode, a skew heap writes the swapped child pointers on the way down the tree while each node is already resident in the L1 CPU cache, whereas a height-biased leftist tree must revisit every ancestor on the way back up. In experimental benchmarks (Jones, 1986; Larkin, Sen, and Tarjan, 2014), top-down skew heaps consistently run faster than leftist trees on random and network-flow workloads such as Dijkstra's algorithm and Prim's algorithm, though two-pass pairing heaps and d-ary array heaps remain faster when Decrease-Key dominates.

Why does unconditional child swapping not undo the balance of an already balanced skew heap?

Even if a node x on the merge path already had a larger left subtree than right subtree (so its left child was heavy and its right child was light), swapping its children turns the heavy left child into a heavy right child—increasing the potential Φ by 1—only when the Meld advances down the light right branch. Because any path contains at most ⌊log₂ n⌋ light edges, at most ⌊log₂ n⌋ such "unhelpful" swaps can occur during the entire Meld, and each one deposits a unit of potential in Φ that pre-pays for swapping that heavy subtree back to the left the very next time a Meld visits x.

Can Insert in a skew heap be improved from O(log n) to O(1) amortized time?

Yes. By observing that inserting a single node is a degenerate Meld where one tree has size 1, Chris Okasaki and Gerth Stølting Brodal (1996) introduced the skew binomial heap (and Schoenmakers analyzed top-down skew heap insertion), showing that insertion into a skew heap actually runs in O(1) amortized time when analyzed with a refined potential function that weights heavy nodes near the bottom of the right spine differently, or in O(1) worst-case time using skew binary numbers.

When should a leftist tree be preferred over a skew heap?

A leftist tree should be chosen over a skew heap in two primary settings: (1) real-time systems where every individual Meld or Delete-Min must finish in guaranteed O(log n) worst-case time without occasional Θ(n) reorganization spikes, and (2) purely functional (persistent) algorithms—such as Eppstein's k-shortest-paths algorithm—where a single historical version of a heap may be melded repeatedly across many branches; in a persistent skew heap, repeating an expensive Θ(n) meld from the same unadjusted historical snapshot breaks the amortized guarantee.

1. Sleator, D. D., & Tarjan, R. E. (1986). "Self-adjusting heaps." SIAM Journal on Computing, 15(1), 52–69. https://doi.org/10.1137/0215004
2. Tarjan, R. E. (1985). "Amortized computational complexity." SIAM Journal on Algebraic and Discrete Methods, 6(2), 306–318. https://doi.org/10.1137/0606031
3. Jones, D. W. (1986). "An empirical comparison of priority-queue and event-set implementations." Communications of the ACM, 29(4), 300–311. https://doi.org/10.1145/5684.5686
4. Brodal, G. S., & Okasaki, C. (1996). "Optimal purely functional priority queues." Journal of Functional Programming, 6(6), 839–857. https://doi.org/10.1017/S095679680000201X
5. Larkin, D. H., Sen, S., & Tarjan, R. E. (2014). "A back-to-basics empirical study of priority queues." In Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX 2014), 61–72. https://doi.org/10.1137/1.9781611973198.7