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

Pairing heaps: meld roots and pair children on removal

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

A pairing heap is a heap-ordered rooted tree whose children are themselves pairing heaps. Meld compares two roots and attaches the larger root beneath the smaller one. Insertion melds a singleton with the current root; merging two queues melds their roots and transfers ownership from the donor. Removing the minimum is the harder operation. The program first melds adjacent children from left to right, then folds those paired trees from right to left. A unique arrival number follows each priority, so equal-priority incidents leave in arrival order even after two queues merge. It exposes push, meld, and pop only; there are no stable node handles or decrease-key operation in this version.

Operational case

Two dispatch teams maintain separate pending queues. East holds pump-47 at priority 47 and valve-19 at 19; West holds sensor-61 at 19 and grid-83 at 61. Melding West into East empties the donor and yields valve, sensor, pump, grid on repeated removal. The equal-priority order comes from arrival numbers assigned before the merge. If each queue restarted its own sequence counter, the two priority-19 entries could compare equal and fall through to a task object or an arbitrary tie. A global sequence in this single-process example avoids that ambiguity.

Working Python program

python
import itertools


arrival_numbers = itertools.count()


class PairingNode:
    def __init__(self, priority, incident_id):
        self.key = (priority, next(arrival_numbers))
        self.incident_id = incident_id
        self.children = []


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

    @staticmethod
    def _meld(left, right):
        if left is None:
            return right
        if right is None:
            return left
        if right.key < left.key:
            left, right = right, left
        left.children.append(right)
        return left

    def push(self, priority, incident_id):
        self.root = self._meld(self.root, PairingNode(priority, incident_id))
        self.size += 1

    def meld(self, other):
        if other is self:
            raise ValueError("cannot meld a heap into itself")
        self.root = self._meld(self.root, other.root)
        self.size += other.size
        other.root = None
        other.size = 0

    def pop(self):
        if self.root is None:
            raise IndexError("empty priority queue")
        removed = self.root
        children = removed.children
        paired = []
        for offset in range(0, len(children), 2):
            paired.append(self._meld(children[offset],
                                     children[offset + 1] if offset + 1 < len(children) else None))
        self.root = None
        for subtree in reversed(paired):
            self.root = self._meld(self.root, subtree)
        self.size -= 1
        return removed.key[0], removed.incident_id


east = PairingIncidentHeap()
west = PairingIncidentHeap()
east.push(47, "pump-47")
east.push(19, "valve-19")
west.push(19, "sensor-61")
west.push(61, "grid-83")
east.meld(west)
print("order=", [east.pop()[1] for _ in range(4)], "donor-size=", west.size, sep="")

Output

Output
order=['valve-19', 'sensor-61', 'pump-47', 'grid-83']donor-size=0

Time, space, and tradeoff

Meld and push perform one root comparison and child append, O(1) under the list-operation model. A single pop can visit every child of the removed root and take O(N) worst-case time; the usual two-pass pairing-heap analysis concerns amortized behavior across operation sequences, not a fixed per-pop deadline. Space is O(N) nodes plus child references. This Python list representation and global sequence are teaching choices, not claims about optimal object overhead or thread safety. A binary heap may be simpler when queues never merge. Self-melding is rejected, and references held to donor nodes should be treated as transferred to the recipient.

Common Mistakes

  • Do not forget the second, right-to-left pairing pass after removing the root.
  • Do not use independent tie counters if merged queues require global arrival order.
  • Do not claim worst-case constant-time removal.
  • Do not keep mutating a donor heap as though meld had copied its nodes.

Connected lessons

Compare its queue operations with Binomial heaps: carry equal-degree trees during merge, Radix heaps: queue nondecreasing integer priorities, Double-ended queues: reconcile min and max heaps, then run the priority-queue audit and contract quiz.

Leftist heaps: keep the right spine short for meld adds a distinct structure contract to compare.

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

data structures
trees-and-heaps
Storage details