↩ back to Node-Linked Trees

Skew Heap

The site's twentieth node-linked trees entry, and a fourth route to the same question Fibonacci Heap, Pairing Heap, and Leftist Heap already answer: a mergeable priority queue. A skew heap goes a step past Leftist Heap's own simplification: it drops the null path length field entirely — no per-node bookkeeping of any kind — and replaces Leftist Heap's compare-then-maybe-swap rule with something even plainer: after every recursive merge step, swap the winning node's two children, unconditionally, no comparison at all. That one rule is the entire structure. The cost of dropping the invariant: unlike Leftist Heap, a single skew-heap merge has no worst-case bound at all — one particular merge can genuinely cost O(n). What survives is an amortized O(log n) bound over any sequence of operations, proven by a potential-function argument rather than a direct per-call guarantee — the same style of bound Splay Tree gives for ordered sets.

Try it

Insert a few values — each one merges a fresh singleton node into the tree by the one rule above. Unlike Leftist Heap's demo, there's no per-node number to watch: skew heap carries no augmented field at all. Extract Min removes the root and merges its two children into a single replacement tree, the same way. The checkbox reproduces a real bug: skip the unconditional swap, and the entire self-adjusting mechanism is gone — there's nothing else holding the tree's shape together.

Core operations

• merge(a, b) — the one primitive everything else is built from, and the only operation this page defines. Compare the two roots; the smaller keeps its own left child and recursively merges the loser into its right child, exactly like Leftist Heap. The difference is what happens once that recursive call returns: unconditionally swap the winner's left and right children — no comparison, no field to consult. The recursion only ever walks down the right spines of a and b, same as Leftist Heap, but nothing bounds how long those spines can be on any single call — see Why the amortized bound holds for what does bound the total cost over many calls.
• insert(x) — merge(heap, singletonTree(x)), same construction as every other heap in this family.
• peek() — the root's own key, the global minimum by the same heap-order argument every entry in this family relies on. O(1).
• extractMin() — remove the root, then merge(root.left, root.right) becomes the new root, identical in shape to Leftist Heap's own extractMin.
• decrease-key — not built here. Not for Leftist Heap's reason (there's no invariant left to break by cutting a node loose — skew heap carries none). The real obstacle is representational: this reference implementation, like Leftist Heap's, keeps no parent pointer on any node, so there's no way to find a node's parent in less than O(n) to detach it in the first place. Pairing Heap and Fibonacci Heap both solve this by maintaining an explicit parent link as part of their own design, specifically to support this operation. Retrofitting one onto a skew heap would make cutting mechanically possible, but a tight amortized bound for repeated cut-and-remerge sequences isn't part of the classic skew-heap analysis the way it's a live, named open question for Pairing Heap specifically — so this page leaves it out rather than present an unproven bound as settled.

Why the amortized bound holds

Define, for any node x with subtree size size(x): x is light if size(x.right) ≤ size(x.left) (its right side is not the bigger side), otherwise heavy. This is a property of the tree's shape alone, not anything skew heap tracks — no field stores it, it's just counted when needed.

Lemma (true of any binary tree, not specific to skew heap): walking down a right spine — x, x.right, x.right.right, … — the number of light nodes encountered is at most ⌊log₂(size(x)+1)⌋. Proof: if y is light, size(y.right) ≤ size(y.left), and since size(y) = 1 + size(y.left) + size(y.right), that forces size(y.right) < size(y)/2. The very next node on the walk is y.right itself, whose subtree is thus under half the size y's was. So every light node the walk passes through at least halves the remaining subtree size — which can happen at most ⌊log₂(size(x)+1)⌋ times before that size hits 1, the same bound Leftist Heap's own right-spine proof reaches, by a different route. Heavy nodes give no such guarantee — a heavy node's right subtree can be almost the whole remaining size — so the walk's raw total length (light nodes and heavy nodes together) isn't bounded by this lemma alone. That's the real gap between the two structures: Leftist Heap's swap rule forces every node it keeps on the right spine into something at least as strong as "light" by construction, bounding the whole spine; skew heap's lemma only bounds the light nodes within a spine of otherwise-unbounded length.

What pays for the heavy nodes is the credit the unconditional swap itself banks. Every node the merge visits gets its children swapped — in particular, every heavy node the merge visits becomes light in the resulting tree, because its new right child is its old (smaller) left subtree. Treating "total heavy nodes in the whole structure" as a potential function, each heavy node a merge is forced to pay real work for immediately converts into banked credit against future merges. Working through exactly how that credit balances out over an arbitrary operation sequence is the potential-function argument Sleator and Tarjan gave when they introduced skew heaps in 1986 (Self-Adjusting Heaps, SIAM J. Computing) — not re-derived line by line here, the same way Pairing Heap's own page cites Fredman's decrease-key bound as literature rather than re-proving it — but the conclusion is the standard, settled result: merge, insert, and extractMin are all O(log n) amortized.

Measured, not just cited: an adversarial single merge built directly from two n-node right-chains (bypassing normal insert/extract-min entirely, so nothing has had a chance to self-adjust in advance) costs exactly 2n − 1 recursive merge calls — 19 at n = 10, 199 at n = 100, 1,999 at n = 1,000, 5,999 at n = 3,000 — genuinely linear, far past any O(log n) bound, confirming a single skew-heap merge really has none. And the very same expensive merge is what pays for the future: the resulting tree's own right spine collapses to exactly 1 node in every one of those runs — that one costly call converts a maximally bad shape into a maximally good one, the concrete shape of the "credit" the potential argument above is accounting for. Over ordinary random usage the amortized bound shows up as a flat, not growing, average: 1,000 / 5,000 / 20,000 / 100,000 interleaved random insert / extract-min calls cost an average of 1.71 / 1.94 / 2.04 / 2.11 recursive merge calls per operation — essentially unchanged as the workload grows 100×, comfortably inside the bound rather than approaching it.

Reference implementation

function merge(a, b) {
  if (a === null) return b;
  if (b === null) return a;
  if (b.key < a.key) { const t = a; a = b; b = t; }
  a.right = merge(a.right, b);
  const t = a.left; a.left = a.right; a.right = t; // unconditional — no comparison
  return a;
}

class SkewHeap {
  #root = null;

  peek() { return this.#root ? this.#root.key : null; }

  insert(key) {
    const node = { key, left: null, right: null };
    this.#root = merge(this.#root, node);
    return node;
  }

  extractMin() {
    if (!this.#root) return null;
    const removed = this.#root.key;
    this.#root = merge(this.#root.left, this.#root.right);
    return removed;
  }
}

Verified with a seeded, reproducible stress harness: 20,000 randomized trials of 40 interleaved insert / extract-min operations each (800,000 operations total), checking after every single operation that (1) the heap-order property holds everywhere and (2) the tree's key set exactly matches an independent oracle array kept in sync by the same operations. Zero failures across all 20,000 trials. The harness was self-tested first against a deliberately broken merge that doesn't pick the smaller root as the new parent — it correctly reported the heap-order property violated. The amortized-cost and adversarial-chain figures in the section above came from the same reference implementation, instrumented with a call counter, not a separate hand count. The shipped demo above runs its own copy of this logic (adapted to log each step, expose a live right-spine readout, and support the buggy checkbox), re-verified the same way against the actual functions extracted from this page's own <script> via Node's vm module driving the real doInsert/doExtract handlers (8,000 more trials, 30 operations each, 240,000 operations total, checking heap order and key set after every single one) — 0 failures, and a same-harness self-test with the buggy checkbox checked confirmed the degeneration below really happens under real button clicks, not just in the standalone script.

Pitfalls

Skipping the swap doesn't break correctness — it removes the entire structure's reason to exist. Try it above: check "skip the unconditional swap," then insert a run of increasing values. peek() and extractMin() keep returning correct answers the whole time — heap order never depended on which child is which — but with the swap gone, every merge just walks straight down the existing right spine and grows it by one, since there's nothing to interrupt that growth. Measured at real scale: inserting 1 through n ascending with the swap disabled leaves a right spine of exactly n nodes — a straight chain — at every size checked from 10 up to 5,000, while the real skew heap on the identical input holds a right spine of 3 / 6 / 9 / 12 nodes at n = 10 / 100 / 1,000 / 5,000. This is the exact same pitfall shape as Leftist Heap's own skip-the-swap bug, but total rather than partial: Leftist Heap without its swap still has a (broken) invariant field sitting there doing nothing; skew heap without its swap has no invariant of any kind left — the whole structure is that one line.

Assuming a single merge is safely fast because the amortized bound is O(log n). It isn't, for any one call in isolation — see the two-chain example in Why the amortized bound holds, where a single merge genuinely costs 2n − 1 recursive calls. That's not a defect to work around; it's the whole trade this structure makes against Leftist Heap. A system that needs every individual call bounded — a hard real-time deadline, a single-request latency SLA — needs Leftist Heap's worst-case guarantee instead; a system that only cares about total throughput over many calls gets skew heap's lower bookkeeping cost for free.

Where skew heaps show up

• Anywhere total throughput matters more than any single call's latency, and even Leftist Heap's one extra integer field feels like bookkeeping not worth carrying. A batch job merging many partial results, or a simulation that only ever measures wall-clock time over its whole run, never one event's own cost, gets the cheapest possible mergeable priority queue: two child pointers, one merge rule, nothing else.
• The self-adjusting family, alongside Splay Tree. Both give up a per-operation worst-case guarantee for an amortized one earned by adjusting shape on every access rather than maintaining an explicit balance invariant — Splay Tree's own page makes the same trade for ordered sets that this page makes for mergeable priority queues, down to both being proven by a potential-function argument rather than a direct inductive bound.
• The structure one step past Leftist Heap's own simplification. Leftist Heap keeps one integer field and a compare-then-maybe-swap rule to buy a worst-case guarantee; skew heap drops the field and the comparison both, keeping only the swap itself, and settles for an amortized bound instead. Same starting point (Leftist Heap's own merge), one further cut.
• Binomial Heap answers the same mergeable-priority-queue question by a completely different route — a forest whose shape is literally the binary representation of its own size — and keeps every operation worst-case rather than amortized, the opposite bargain from this page's own.

Complexity

Time: merge, insert, and extractMin are all O(log n) amortized — a bound on the total cost of any sequence of operations, not on any single call in isolation the way Leftist Heap's worst-case guarantee is; see Why the amortized bound holds for a measured example of one call alone costing O(n). peek is O(1). decrease-key is not built (see Core operations). Space: O(n) — one node per element, holding only two child pointers and nothing else: no augmented field of any kind, cheaper even than Leftist Heap's single extra integer, and far cheaper than Pairing Heap's or Fibonacci Heap's parent-pointer bookkeeping.

This site's guide, Choosing a Search Tree, groups this entry with Fibonacci, Pairing, Leftist, and Binomial Heap as a mergeable priority queue rather than an ordered set — none of the five supports a general search for an arbitrary key. Among them, it goes furthest past Leftist Heap's own simplification: no augmented field at all, just an unconditional child swap instead of a compare-then-swap rule, settling for the same kind of amortized bound Pairing Heap does — proven, rather than left open.