Skew Heaps

Skew heaps are small mergeable priority queues. They store a heap-ordered binary tree and make merge the only structural operation. Insert merges a singleton, and extract-min merges the old root’s children.

The structure is a self-adjusting relative of the leftist heap. A leftist heap stores null-path length and swaps children only when its invariant requires it. A skew heap stores no rank. After descending a right spine, it swaps both children at every touched node, moving the path that just grew away from the route used by the next merge.

Core shape: heap-ordered binary tree, no rank field → merge recurses down right spines → swap children at every merged node

Use Merge on the heaps [2, 7, 10] and [3, 5, 8]. Every touched node swaps its children, regardless of shape. Reset restores both inputs.

VisualizationVisualizationComplexityComplexity

Visualization

Why the Blind Swap Balances

Merge takes two heap roots and compares them. The smaller root becomes the result’s root; its right subtree is merged recursively with the other whole heap; then the root’s two children are swapped. Only the right spine is ever descended, so the recursion depth is the combined right-spine length of the two inputs.

The unconditional swap breaks that: every node on the traversed spine has its freshly extended right child rotated to the left, out of the path future merges follow. A leftist heap achieves the same shortening deliberately, keeping the shorter subtree on the right by consulting the stored null-path length; the skew heap achieves it blindly, and pays for the difference in the analysis rather than in per-node memory.

The invariant that survives every operation is heap order alone: a parent key never exceeds a child key. There is no structural invariant on shape — a skew heap can momentarily be a long right chain. Insert merges a singleton node into the heap. Extract-min removes the root and merges its two children. Both inherit merge’s cost profile exactly.

Complexity

TimeSpace

Merge(a, b)

• Best: O(1)
• Amortized: O(log n)
• Worst single op: O(n)

Insert(x)

• Best: O(1)
• Amortized: O(log n)
• Worst single op: O(n)

ExtractMin()

• Best: O(1)
• Amortized: O(log n)
• Worst single op: O(n)

FindMin()

• Best/Amortized: O(1)
• Worst single op: O(1)

n

total stored nodes, combining both input heaps for merge

Persistence widens the difference. A leftist heap’s worst-case bound applies to each operation, even when versions share subtrees. A skew heap spreads cost across an update sequence. Branching repeatedly from older versions needs a separate sequence analysis.

The unconditional swap is the entire adjustment mechanism. There is no rank to inspect, so skipping the swap produces a different structure and invalidates the usual potential argument.

Diagram and C# Implementation

Merge folding the right spine

flowchart LR
  subgraph before [Two heaps]
    A2((2)) --> A5((5))
    A2 --> A9((9))
    B3((3)) --> B4((4))
    B3 --> B8((8))
  end
  subgraph after [Merged, children swapped at each touched node]
    M2((2)) --> M3((3))
    M2 --> M5((5))
    M3 --> M4((4))
    M3 --> M8((8))
    M8 --> M9((9))
  end
  before --> after

C# implementation

public sealed class SkewHeap<T> where T : IComparable<T>
{
    private sealed class Node
    {
        public T Key = default!;
        public Node? Left;
        public Node? Right;
    }
 
    private Node? _root;
 
    public T FindMin() =>
        _root is null ? throw new InvalidOperationException("empty") : _root.Key;
 
    public void Insert(T key) =>
        _root = Merge(_root, new Node { Key = key });
 
    public T ExtractMin()
    {
        if (_root is null) throw new InvalidOperationException("empty");
        var min = _root.Key;
        _root = Merge(_root.Left, _root.Right);
        return min;
    }
 
    private static Node? Merge(Node? a, Node? b)
    {
        if (a is null) return b;
        if (b is null) return a;
 
        if (a.Key.CompareTo(b.Key) > 0)
        {
            (a, b) = (b, a);
        }
 
        // Descend the right spine, then swap children unconditionally.
        a.Right = Merge(a.Right, b);
        (a.Left, a.Right) = (a.Right, a.Left);
        return a;
    }
}

The two swap-carrying lines are the entire self-adjustment: there is no rank field to update and no condition guarding the swap. Removing the swap, or making it conditional on stored metadata, produces a different data structure.

References

• Sleator & Tarjan, “Self-Adjusting Heaps” (SIAM J. Comput. 1986)