Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Leftist heaps: keep the right spine short for meld

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A leftist heap is a min-heap with an extra rank: the shortest path from a node to an absent child, counting a leaf as rank one and an absent node as zero. The left child's rank must be at least the right child's rank. Meld selects the smaller root, recursively merges the other heap into its right child, swaps children if their ranks are out of order, then repairs the root rank. The short right spine bounds merge work. This dispatch example orders by (priority, case ID), so equal priorities have a deterministic ID tie. Merge transfers the donor's nodes and empties its public handle; callers must not continue treating the donor as an independent owner of those nodes.

Operational case

East dispatch has cases (4,47), (2,83), and (4,19). West has (1,61) and (3,29). Melding West into East produces extraction order (1,61), (2,83), (3,29), (4,19), (4,47). West then reports size zero. If both heap handles retained the same root after merge, popping through either could mutate the other's structure, breaking ownership and rank assertions. A self-merge is rejected for the same reason. This implementation accepts duplicate case IDs if their priority pairs differ; a service that requires one live entry per ID needs a separate keyed membership or handle index.

Working Python program

python
class DispatchNode:
    def __init__(self, priority, case_id):
        self.key = (priority, case_id)
        self.left = None
        self.right = None
        self.rank = 1


def null_rank(node):
    return node.rank if node else 0


def meld(first, second):
    if first is None:
        return second
    if second is None:
        return first
    if second.key < first.key:
        first, second = second, first
    first.right = meld(first.right, second)
    if null_rank(first.left) < null_rank(first.right):
        first.left, first.right = first.right, first.left
    first.rank = 1 + null_rank(first.right)
    return first


class LeftistDispatchHeap:
    def __init__(self):
        self.root = None
        self.count = 0

    def push(self, priority, case_id):
        self.root = meld(self.root, DispatchNode(priority, case_id))
        self.count += 1

    def merge_from(self, other):
        if self is other:
            raise ValueError("cannot meld a heap with itself")
        self.root = meld(self.root, other.root)
        self.count += other.count
        other.root, other.count = None, 0

    def pop(self):
        if self.root is None:
            raise IndexError("empty dispatch heap")
        key = self.root.key
        self.root = meld(self.root.left, self.root.right)
        self.count -= 1
        return key


east, west = LeftistDispatchHeap(), LeftistDispatchHeap()
for priority, case_id in [(4, 47), (2, 83), (4, 19)]:
    east.push(priority, case_id)
for priority, case_id in [(1, 61), (3, 29)]:
    west.push(priority, case_id)
east.merge_from(west)
print([east.pop() for _ in range(east.count)], west.count)

Output

Output
[(1, 61), (2, 83), (3, 29), (4, 19), (4, 47)] 0

Time, space, and tradeoff

The right spine of a leftist heap has O(log N) length because each node of rank r roots at least 2^r-1 nodes. Meld, push through singleton meld, and pop through child meld therefore take O(log N) worst-case time and recursive stack space here; reading the minimum is O(1). Storage is O(N) nodes with one rank each. This offers a stronger stated merge bound than the simple two-pass pairing model in this curriculum, but it still does not supply an indexed decrease-key operation. Python object pointers and recursion add overhead; an array heap may remain a better choice when queues never need to merge.

Common Mistakes

  • Do not forget to swap children before recomputing the rank.
  • Do not leave the donor handle pointing at transferred nodes.
  • Do not assume equal priorities have stable insertion order here.
  • Do not advertise decrease-key without a handle and repair protocol.

Connected lessons

Compare its update and query contract with Eytzinger arrays: store a search tree in breadth-first order, Cartesian trees: preserve sequence order under a heap minimum, Potential disjoint sets: preserve numeric differences across merges, then complete the structure audit and decision quiz.

Skew heaps: meld priorities by swapping child paths adds a related structure with a different operation boundary.

data structures
trees-and-heaps
Storage details