Cairn
data structures · twenty-first Node-Linked Trees entry · O(log n) worst-case merge / insert / extract-min / decrease-key

↩ back to Node-Linked Trees

Binomial Heap

The site's twenty-first node-linked trees entry, and the one genuine gap left in its own mergeable-priority-queue family: Fibonacci Heap, Pairing Heap, Leftist Heap, and Skew Heap all answer the same question — insert, find-min, extract-min, merge two heaps into one — but not one of those four pages ever names the structure that came first. J. Vuillemin invented the binomial heap (he called it a binomial queue) in 1978, six years before Fredman and Tarjan built the Fibonacci heap specifically to go faster at one operation this page also builds: decrease-key. A binomial heap gives every single operation — not just the average over a long run — an O(log n) ceiling, including decrease-key. That is the one combination none of the four newer pages offer: Fibonacci and Pairing Heap only get decrease-key to O(1) by settling for an amortized bound, and Leftist and Skew Heap sidestep the question entirely by not building decrease-key at all. This page is the "no free lunch, no shortcuts" member of the family — every call, on its own, provably bounded — and its shape does something none of the other four can claim either: the forest of trees it maintains is, digit for digit, the binary representation of how many elements it holds.

Try it

Insert a few values and watch the forest below the controls — and watch the binary readout in the log line under it. Every heap holds at most one tree of each degree, a tree of degree k always has exactly 2^k nodes, and a tree exists at degree d if and only if bit d of the current size is set. Insert enough values to watch a run of trees collapse into one bigger tree — that's a carry, the same thing that happens when a binary counter rolls from 0111 to 1000. Click any node to select it, then Decrease Key to lower it below its parent and watch it bubble straight up its own tree, swapping places with each ancestor along the way, until it either reaches the root or stops being smaller than its new parent.

Loaded a sample forest. Insert, extract, or click a node then decrease its key.

Core operations

Why it works: the forest is a binary counter

Every other mergeable heap on this site earns its bound from a per-node invariant (Leftist Heap's null-path-length field) or a potential-function argument over an amortized sequence (Fibonacci Heap's marks, Skew Heap's heavy/light argument). A binomial heap earns its bound from something much more literal: at any moment, its forest holds at most one tree per degree, and a tree of degree d always holds exactly 2^d nodes — so the presence or absence of a tree at each degree is exactly one bit of the heap's size, written in binary, from degree 0 (the ones bit) upward. A heap holding 13 elements (binary 1101) has, and can only have, trees of degree 3, 2, and 0. There's no other valid shape for 13 elements, ever — the forest's shape isn't a design choice made by whichever sequence of inserts and merges built it, it's forced entirely by n itself.

Why merge behaves like binary addition. Combining two forests means combining two binary numbers, and combining numbers digit-by-digit-with-carry is precisely what merge does: at each degree, link is the operation that turns "two trees of degree d" into "one tree of degree d+1, carried up" — the exact shape of a full adder's carry-out. Because both input forests have at most O(log n) trees, and the whole pass is one linear walk over degrees with O(1) work each, merge is O(log n), full stop — not an average, an actual bound on every single call, because the number of degrees a forest can span is bounded on every single call, not just typically.

Why insert is worst-case O(log n) but amortized O(1). This is the exact same accounting Fibonacci Heap's own lazy inserts and Dynamic Array's doubling resize both rely on, just applied to a binary counter instead of a growing array: incrementing 0111 to 1000 ripples through three carries, but most increments touch only the last bit or two. Charge each carry to the insert that originally set the bit it's now clearing, and the books balance across any sequence — see the measured link counts in Pitfalls for the exact numbers, not just the argument. decrease-key gets no equivalent discount. Its cost is the height of whichever tree the target node sits in, and nothing about repeated calls makes that height shrink or spreads the cost elsewhere the way a carry chain's cost gets paid down by the inserts that caused it — every single call really does cost up to O(log n), which is exactly why this page's own headline claim is a genuine worst-case bound, not an amortized one dressed up to look like one.

Reference implementation

class BNode {
  constructor(key) {
    this.key = key;
    this.degree = 0;
    this.parent = null;
    this.children = [];   // children[0] is the most-recently-attached (highest-degree) child
  }
}

class BinomialHeap {
  #trees = [];             // sparse array indexed by degree; #trees[d] is a root or undefined
  #size = 0;
  #min = null;

  get size() { return this.#size; }
  peek() { return this.#min ? this.#min.key : null; }

  #refreshMin() {
    this.#min = null;
    for (const t of this.#trees) if (t && (this.#min === null || t.key < this.#min.key)) this.#min = t;
  }

  static #link(y, x) { y.parent = x; x.children.unshift(y); x.degree++; return x; }

  static #merge(a, b) {
    const len = Math.max(a.length, b.length) + 1;
    const out = new Array(len).fill(undefined);
    let carry;
    for (let d = 0; d < len; d++) {
      const bits = [a[d], b[d], carry].filter(Boolean);
      carry = undefined;
      if (bits.length === 0) { out[d] = undefined; }
      else if (bits.length === 1) { out[d] = bits[0]; }
      else if (bits.length === 2) {
        out[d] = undefined;
        const [p, q] = bits;
        carry = p.key <= q.key ? BinomialHeap.#link(q, p) : BinomialHeap.#link(p, q);
      } else {                                    // all three slots occupied — keep one, link the other two
        out[d] = bits[0];
        const [, p, q] = bits;
        carry = p.key <= q.key ? BinomialHeap.#link(q, p) : BinomialHeap.#link(p, q);
      }
    }
    while (out.length && out[out.length - 1] === undefined) out.pop();
    return out;
  }

  insert(key) {
    const node = new BNode(key);
    this.#trees = BinomialHeap.#merge(this.#trees, [node]);
    this.#size++;
    this.#refreshMin();
    return node;
  }

  extractMin() {
    if (this.#size === 0) return null;
    const min = this.#min;
    const childTrees = [];
    for (const c of min.children) { c.parent = null; childTrees[c.degree] = c; }
    const remaining = this.#trees.slice();
    remaining[min.degree] = undefined;
    this.#trees = BinomialHeap.#merge(remaining, childTrees);
    this.#size--;
    this.#refreshMin();
    return min.key;
  }

  decreaseKey(node, newKey) {
    if (newKey >= node.key) return false;
    node.key = newKey;
    let cur = node;
    while (cur.parent && cur.parent.key > cur.key) {
      const p = cur.parent;
      [cur.key, p.key] = [p.key, cur.key];
      cur = p;
    }
    if (this.#min === null || cur.key < this.#min.key) this.#min = cur;
    return true;
  }
}

Verified with a seeded, reproducible stress harness: 20,000 randomized trials of 40 interleaved insert / extract-min / decrease-key calls each (800,000 operations total), checking after every single operation that (1) every tree's heap-order property holds top to bottom, (2) every tree of degree d has exactly d children whose degrees are exactly {0, 1, ..., d-1} — the structural definition of a binomial tree, not just heap order — (3) a tree exists at degree d if and only if bit d of the heap's current size is set, checked against the real binary representation of n at every step, (4) the full multiset of live keys matches an independent oracle array's, and (5) the cached min pointer's key matches that same oracle's true minimum. Zero failures across all 800,000 operations. The harness was self-tested first against two deliberately broken copies of this exact model — one that always links the second tree under the first regardless of which key is smaller (19,984 of 20,000 trials failed, almost always on the very first merge), and one where decreaseKey never refreshes the min pointer after bubbling a node past the current minimum (7,070 of 20,000 trials failed) — both caught immediately, confirming the checks have real teeth before trusting a clean run on the real model to mean anything.

The shipped demo above runs its own copy of this logic (adapted to log each step and expose live node identities for click-to-select, instead of returning silently) — extracted the actual functions out of this page's own <script> via Node's vm module and re-ran an equivalent 8,000-trial harness (over 300,000 more operations) driving the real Insert / Extract Min / Decrease Key button handlers through simulated clicks, same five checks as above. Zero mismatches.

Pitfalls

Insert is not worst-case O(1) here, unlike Fibonacci Heap. Fibonacci Heap's insert is genuinely constant on every call — it never merges anything until the next extractMin forces it to. This structure has no such lazy escape hatch: every insert immediately merges, so a long run of trailing 1-bits in the current size means a long carry chain right now. Directly instrumenting the reference model confirms the exact shape of this cost rather than asserting it: inserting one more element into a heap already sized at 3, 7, 15, 31, 63, 127, 255, 1023, and 32,767 (each one less than a power of two — every bit set) triggers exactly 2, 3, 4, 5, 6, 7, 8, 10, and 15 link operations respectively, matching the count of trailing 1-bits exactly at every size tested — a real, measured O(log n) worst case, not a theoretical one that never actually shows up.

decrease-key's bound has no amortized rescue, and that's structural, not a missed optimization. Measured directly: build a single tree of degree k (exactly 2^k elements, one tree, no other shape is possible at that size) for k = 4, 8, 12, and 16, then find the node buried deepest in it. It sits exactly 4, 8, 12, and 16 levels down every time — precisely k, never less — and decreasing that one node's key bubbles it the full k levels to become the new root every time. Unlike this page's own insert cost, there is no cheaper amortized story to tell here: nothing about a sequence of prior operations pays this cost down, because the tree's shape never changes on a decrease-key call the way a lazy insert's un-consolidated root list does. This is exactly the structural cost Fibonacci Heap's cut-and-cascade machinery exists to avoid — by tearing the tree apart on every decrease-key instead of preserving it, Fibonacci Heap trades this page's honest worst-case guarantee for an amortized O(1) one.

A count-of-three merge step is easy to get wrong by assuming only two trees can ever collide at one degree. A first-draft implementation that only checks a[d] against b[d] and forgets a carry can arrive at the same degree simultaneously — the genuine three-way case a full binary-addition analogy demands — silently drops one of the three trees on the floor instead of correctly keeping one and carrying two. The stress harness's key-set check (item 4 above) catches this immediately, but only because it compares the full multiset against an oracle after every call; a check that only verifies heap order or degree shape on the surviving trees would never notice a whole tree quietly vanishing.

Where binomial heaps show up

Complexity

Time: link is O(1). merge is O(log n) worst case, where n is the combined size of both heaps — one pass over at most O(log n) degrees. insert is O(log n) worst case (a full carry chain), O(1) amortized (see Why it works). peek is O(1) via the cached min pointer. extractMin is O(log n) worst case — scanning up to O(log n) roots plus one merge. decreaseKey is O(log n) worst case, bounded by the height of the tree the target node sits in, with no amortized discount (see Pitfalls). Space: O(n) — one node per element, each carrying a parent pointer and a children list, the same per-node overhead as every other tree-based heap on this site.

This site's guide, Choosing a Search Tree, groups this entry with Fibonacci, Pairing, Leftist, and Skew Heap as answering a different question than the guide's own seven comparison entries — a mergeable priority queue, not an ordered set, with no general search for an arbitrary key. Among those five, it's the oldest (Vuillemin, 1978, the structure Fibonacci Heap was built to beat) and the only one that bounds every operation, including decreaseKey, worst-case rather than amortized — the "no free lunch" combination none of the other four offer.