Binomial Queues and the Carry Chain of Merges

A binomial queue is a collection of heap-ordered trees rather than a single tree, and the collection is structured so that a merge of two queues is exactly the addition of two binary numbers. The analogy is not decorative: the number of trees of each size encodes the total element count in binary, the merge performs carries, and the amortised cost of insertion falls out of the fact that binary increment flips an amortised constant number of bits. The structure was introduced by Vuillemin in 1978 and remains the clearest example of a lazy data structure whose complexity is explained by an unrelated arithmetic process.

A forest whose shape encodes the count

A binomial tree of order k, written B_k, is defined recursively: B_0 is a single node, and B_k is formed by linking two B_(k−1) trees, making the root of one the leftmost child of the other. The definition forces the shape: B_k has exactly 2^k nodes, its root has k children, and the i-th child is the root of a B_i tree. A B_3, for instance, holds 8 nodes: the root has children that are roots of B_0, B_1, and B_2, holding 1, 2, and 4 nodes respectively.

The count is what matters. Since B_k holds 2^k nodes, any set of n elements can be partitioned into at most one tree of each order, corresponding to the binary representation of n. A queue of 13 elements holds a B_3, a B_2, and a B_0 — 8 + 4 + 1 — because 13 is 1101 in binary. The forest is therefore never larger than ⌊log₂ n⌋ + 1 trees, and the position of a tree in the forest is determined by the element count alone.

Each tree satisfies the heap property: a parent’s key is no larger than any descendant’s. Nothing more is required. There is no balance condition, no rank, and no constraint on sibling order beyond the structural definition.

Linking is the primitive

Two binomial trees of the same order k are combined by a link: compare their roots, and make the larger root the leftmost child of the smaller. The result is a valid B_(k+1), because the definition of that tree is precisely “two B_k trees with one root attached under the other”, and the heap property survives since the new child’s root was the larger of the two.

Link costs O(1): one comparison, one pointer assignment, and an update to the child list. Everything else in the structure is built from links.

Merging two queues follows binary addition exactly. Walk the orders from 0 upward, carrying:

• if neither queue has a tree of order k and no carry is pending, nothing happens;
• if exactly one of the three (queue A, queue B, carry) has a tree of order k, that tree becomes the result’s tree of order k;
• if two of them have one, link them into a B_(k+1) and carry;
• if all three have one, the two from the queues link into a B_(k+1) which becomes the carry, and the pending carry becomes the result’s tree of order k.

/* Add one tree of order k to a forest, carrying as binary addition would. */
static void forest_add(forest *f, int k, bnode *t) {
    while (f->tree[k]) {                 /* slot occupied: link the two and carry */
        bnode *cur = f->tree[k];
        if (cur->key <= t->key) { t->next = cur->child; cur->child = t; t = cur; }
        else                    { cur->next = t->child;  t->child  = cur; }
        f->tree[k] = NULL;
        k++;
    }
    f->tree[k] = t;
}

Merging two queues is then a loop that calls forest_add once per tree in either input, and the routine’s own carry chain performs the links. Its depth is bounded by the number of orders, about log₂ n, and each step does constant work. A merge of queues holding n and m elements costs O(log(n + m)) in the worst case, because the carry chain can propagate across every order — exactly as adding 1 to 0111…1 flips every bit.

Insertion is a merge with a single-node queue, so it too is O(log n) worst case. The interesting part is the amortised bound. Number the insertions and look at the carry chain: insertion i links trees exactly at the positions where the binary representation of i ends in ones, so the number of links is the number of trailing ones in i. That count is 0 for every even i, 1 for every i ≡ 2 (mod 4), and so on; over n insertions the total is less than 2n. The amortised cost of insertion is therefore O(1) — the same accounting that makes binary increment O(1) amortised.

Extract-min decomposes the forest

Finding the minimum requires scanning the roots of at most ⌊log₂ n⌋ + 1 trees, since the heap property only guarantees that the minimum of each tree is its root. That scan is O(log n), and it is the only place the structure pays for having many trees.

Removing that root splits its tree. If the minimum was the root of a B_k, its children are roots of B_0 through B_(k−1), and each of those is already a valid binomial tree. Detaching them yields a new forest containing one tree of every order from 0 to k − 1 — a queue holding 2^k − 1 elements, represented by k trees. Merging that forest with the remainder of the original queue costs O(log n), so extract-min is O(log n) overall, dominated by the root scan.

/* Union of two forests: move every tree of src into dst, carrying by order. */
static void forest_union(forest *dst, forest *src) {
    for (int k = 0; k <= MAX_ORDER; k++)
        if (src->tree[k]) { forest_add(dst, k, src->tree[k]); src->tree[k] = NULL; }
}

static bnode *extract_min(forest *f) {
    int best = -1;
    for (int k = 0; k <= MAX_ORDER; k++)
        if (f->tree[k] && (best < 0 || f->tree[k]->key < f->tree[best]->key)) best = k;
    bnode *t = f->tree[best];
    f->tree[best] = NULL;
    forest rest = {0};
    /* Children of a B_k are roots of B_0 .. B_{k-1}, in decreasing order. */
    bnode *c = t->child;
    int k = best - 1;
    while (c) { bnode *nx = c->next; c->next = NULL; rest.tree[k--] = c; c = nx; }
    forest_union(f, &rest);          /* O(log n): k trees into the remaining forest */
    return t;
}

The child list must be in decreasing order of subtree size for the detachment loop to place each child at the right order index. That is why link attaches the new child at the front of the child list: the most recently linked tree is the largest, so the list stays sorted by decreasing order, and the detachment walks it directly.

Decrease-key needs a parent pointer per node. With it, lowering a key and sifting up along the parent chain costs O(log n), since a node’s depth in a B_k is at most k. Without it, the operation is not available at all.

The pointer cost and the layout problem

A binomial node typically holds a key, a pointer to its parent, a pointer to its leftmost child, and a pointer to its next sibling — five words, forty bytes on a 64-bit build, against four bytes per key for an array of 32-bit keys. For a million elements the nodes occupy roughly 40 MB against 4 MB of keys, and the ratio worsens for smaller keys.

Worse than the total is the access pattern. A root scan touches the roots of up to twenty trees, which are separate allocations scattered in the heap. An extract-min detaches a child list, which is the one traversal with locality — siblings are linked, though not necessarily adjacent in memory. Every operation is a sequence of dependent loads, and the structure’s asymptotic advantage over an array heap appears only when the operation mix includes many merges of large queues, where the array heap would pay linear time.

Memory management is a second concern. Extracting the minimum detaches a child list and then merges it back, so nodes change parent and sibling links repeatedly but are never freed until the whole queue is destroyed or a node is explicitly removed. Only the extracted root leaves the forest, so the queue holds n − 1 nodes afterwards. That is a genuine advantage over lazy-deletion schemes that accumulate duplicates. The cost is that node lifetime is tied to the queue rather than to the element, so removing an arbitrary element requires unlinking it from its parent’s child list — a scan of that list, bounded by the order but not constant.

Where the structure earns its keep

Binomial queues matter less as an implementation choice than as a conceptual step. They establish that a priority queue can be a forest whose shape encodes the element count, that merge can be made to look like addition, and that insertion can be amortised constant without any restructuring rule. The Fibonacci heap takes the next step: it stops linking eagerly during a merge, leaving trees of equal order side by side, and defers the cleanup to extraction, which is what buys O(1) amortised decrease-key — see Fibonacci heaps and the decrease-key argument. Pairing heaps take a different step in the same direction, replacing the order bookkeeping with a two-pass merge over a plain child list, as described in pairing heaps and self-adjusting merges.

The direct use of binomial queues is in settings where the merge bound is the binding constraint and the element count is moderate. A merge of two queues is O(log n) with a small constant: for a random element count each bit is occupied with probability about one half, so the carry chain terminates after an expected constant number of links. The worst case is logarithmic, but the expected case is a handful of links.