Skew heaps: meld priorities by swapping child paths

Last updated: 7 Oct 20269 min read

tutorial

A skew heap is a heap-ordered binary tree whose core operation melds two roots. The smaller root stays above; its right subtree is melded with the other heap, then its left and right children swap. No null-path rank is stored. Push melds a singleton node, and pop removes the current root by melding its two children. This implementation compares priority first and task ID second, giving reproducible ties. A merge-from operation transfers the donor root and clears the donor, so the same mutable nodes are never owned by two live heap objects. The tree can be skewed after one operation even though operation sequences have a useful amortized bound.

Operational case

Two dispatch queues hold priorities 47 and 19 in one heap and 61 and 29 in another. After transfer, popping four times returns tasks in 19, 29, 47, 61 priority order, and the donor has size zero. If the donor retained its root, a later pop on either owner would mutate nodes still reachable from the other queue. The example lacks direct handles and decrease-key; changing a task's priority requires a separate indexed design or reinsertion policy that prevents an obsolete entry from winning.

Working Python program

class DispatchNode:
    def __init__(self, priority, task_id):
        self.priority, self.task_id = priority, task_id
        self.left = None
        self.right = None


def meld_nodes(first, second):
    if first is None:
        return second
    if second is None:
        return first
    if (second.priority, second.task_id) < (first.priority, first.task_id):
        first, second = second, first
    first.right = meld_nodes(first.right, second)
    first.left, first.right = first.right, first.left
    return first


class DispatchSkewHeap:
    def __init__(self):
        self.root = None
        self.size = 0

    def push(self, priority, task_id):
        self.root = meld_nodes(self.root, DispatchNode(priority, task_id))
        self.size += 1

    def merge_from(self, donor):
        if donor is self:
            raise ValueError("cannot meld heap into itself")
        self.root = meld_nodes(self.root, donor.root)
        self.size += donor.size
        donor.root, donor.size = None, 0

    def pop(self):
        if self.root is None:
            raise IndexError("empty heap")
        minimum = self.root
        self.root = meld_nodes(minimum.left, minimum.right)
        self.size -= 1
        return minimum.priority, minimum.task_id


if __name__ == "__main__":
    urgent, routine = DispatchSkewHeap(), DispatchSkewHeap()
    for priority, task in [(47, "T-47"), (19, "T-19")]:
        urgent.push(priority, task)
    for priority, task in [(61, "T-61"), (29, "T-29")]:
        routine.push(priority, task)
    urgent.merge_from(routine)
    print([urgent.pop() for _ in range(4)])
    print(routine.size)

Output

[(19, 'T-19'), (29, 'T-29'), (47, 'T-47'), (61, 'T-61')]
0

Time, space, and tradeoff

Meld, push, and pop have O(log N) amortized time over operation sequences but O(N) worst-case time for a single highly skewed operation. This recursive Python form can also hit recursion limits on an adverse long path. Each node stores two child pointers and a priority pair, giving O(N) heap space; meld uses O(H) call-stack space for path height H. A leftist heap keeps rank metadata for a worst-case logarithmic right spine, while a binary heap may be simpler when melding is not needed. No empirical speed claim follows from these bounds.

Common Mistakes

Do not retain a mutable donor root after transferring ownership.
Do not report worst-case logarithmic time for every individual meld.
Do not forget the child swap after melding down the right path.
Do not present this model as supporting decrease-key by task handle.

Connected lessons

Compare its input and update contract with CSR delta overlays: stage road edits before compaction, Reachability bitsets: precompute directed paths for a fixed graph, Gap labels: compare dispatch order across middle inserts, then complete the structure audit and decision quiz.

data structures

trees-and-heaps