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

Binomial heaps: carry equal-degree trees during merge

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

A binomial heap is a forest with at most one heap-ordered tree of each degree. Linking two degree-D trees makes the larger root a child of the smaller root, producing one degree-D-plus-one tree. The forest therefore behaves like a binary count: equal degrees carry into the next degree. This implementation stores roots by degree, merges a singleton or another forest by repeated carries, and extracts the smallest root before returning its children to the forest. It compares priority followed by one process-wide arrival number to preserve stable ties across merged queues. A meld transfers the donor's roots and leaves the donor empty. There is no decrease-key or arbitrary-node deletion API.

Operational case

East and West each hold two incident tasks. Their merge may have two degree-one roots, which must link into one degree-two tree; leaving both roots at degree one breaks the representation invariant. The merged queue returns valve-19 and sensor-61 before pump-47 and grid-83. Emptying the donor is part of the ownership contract, not an optimization detail. A checker can recursively count nodes in each tree and compare its size with two raised to its degree, then verify that every parent priority is no greater than its children.

Working Python program

python
import itertools


arrival_numbers = itertools.count()


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


class BinomialIncidentHeap:
    def __init__(self):
        self.roots = {}
        self.size = 0

    @staticmethod
    def _link(left, right):
        if right.key < left.key:
            left, right = right, left
        left.children.append(right)
        left.degree += 1
        return left

    def _add_tree(self, tree):
        while tree.degree in self.roots:
            tree = self._link(tree, self.roots.pop(tree.degree))
        self.roots[tree.degree] = tree

    def push(self, priority, incident_id):
        self._add_tree(BinomialNode(priority, incident_id))
        self.size += 1

    def meld(self, other):
        if other is self:
            raise ValueError("cannot meld a heap into itself")
        for tree in list(other.roots.values()):
            self._add_tree(tree)
        self.size += other.size
        other.roots.clear()
        other.size = 0

    def pop(self):
        if not self.roots:
            raise IndexError("empty priority queue")
        degree = min(self.roots, key=lambda level: self.roots[level].key)
        removed = self.roots.pop(degree)
        for subtree in removed.children:
            self._add_tree(subtree)
        self.size -= 1
        return removed.key[0], removed.incident_id


east = BinomialIncidentHeap()
west = BinomialIncidentHeap()
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

For N entries, a forest has at most O(log N) roots. Push, meld, and pop perform O(log N) tree links or root scans in the worst-case structural model; finding the minimum here scans the roots rather than storing a separate pointer. Space is O(N) nodes and child references. Python dictionary operations add expected hashing costs, and the stated structural bounds do not promise hard real-time latency. The forest representation pays more pointer overhead than an array heap, but melding it does not require inserting all donor entries one by one. This direct code assumes single-process ownership and does not synchronize concurrent producers.

Common Mistakes

  • Do not retain two roots with the same degree after a carry.
  • Do not discard the removed root's children during extraction.
  • Do not call the donor independently usable after ownership transfer.
  • Do not promise constant-time minimum lookup when roots are scanned.

Connected lessons

Compare its queue operations with Pairing heaps: meld roots and pair children on removal, 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.

Fibonacci heaps: cut on decrease and consolidate on removal adds a related structure with a different operation boundary.

data structures
trees-and-heaps
Storage details