AlgoScope

Binomial and Fibonacci Heaps

A binary heap is one tree, so merging two of them means rebuilding. A binomial heap is a forest instead: one tree of each size that appears in the binary expansion of n, and merging two heaps is binary addition, where two trees of the same degree link with the larger root under the smaller and carry to the next degree. A Fibonacci heap takes the same forest and stops tidying it: insert and merge just add roots, and only extract-min pays the bill by linking equal degrees until every degree is unique. That laziness is what buys the famous decrease-key: a node whose key drops below its parent is simply cut to the root list in O(1), with cascading cuts on marked ancestors so no tree gets too thin for the degree bound to hold.

The player

Merging two binomial heaps.heap301045205512358

Merge a heap of 5 keys, held as B0, B2, with a heap of 3 keys, held as B0, B1. Put both root lists together and walk the degrees from 0 upward: one tree of a degree stays, two link into the next degree, three link two and leave one. It is binary addition, 5 + 3 = 8, tree by tree.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 4, with their answers.

  1. There are 2 trees of degree 0. What happens at this degree?

    • One tree of degree 0: it stays
    • Two trees of degree 0: link them into a B1
    • Three trees of degree 0: link two, one stays

    Answer: Two trees of degree 0: link them into a B1. Exactly like adding binary digits: 1 stays, 2 carries, 3 carries and leaves 1.

  2. There are 2 trees of degree 1. What happens at this degree?

    • One tree of degree 1: it stays
    • Two trees of degree 1: link them into a B2
    • Three trees of degree 1: link two, one stays

    Answer: Two trees of degree 1: link them into a B2. Exactly like adding binary digits: 1 stays, 2 carries, 3 carries and leaves 1.

  3. There are 2 trees of degree 2. What happens at this degree?

    • One tree of degree 2: it stays
    • Two trees of degree 2: link them into a B3
    • Three trees of degree 2: link two, one stays

    Answer: Two trees of degree 2: link them into a B3. Exactly like adding binary digits: 1 stays, 2 carries, 3 carries and leaves 1.

  4. There are 1 tree of degree 3. What happens at this degree?

    • One tree of degree 3: it stays
    • Two trees of degree 3: link them into a B4
    • Three trees of degree 3: link two, one stays

    Answer: One tree of degree 3: it stays. Exactly like adding binary digits: 1 stays, 2 carries, 3 carries and leaves 1.

How it runs, step by step

  1. Merge a heap of 5 keys, held as B0, B2, with a heap of 3 keys, held as B0, B1. Put both root lists together and walk the degrees from 0 upward: one tree of a degree stays, two link into the next degree, three link two and leave one. It is binary addition, 5 + 3 = 8, tree by tree.

    Merging two binomial heaps.

  2. Degree 0: 2 trees, rooted at 55, 8. Two of a kind: link them, and the result is a B1 that joins the next degree.

    Degree 0: 2 trees.

  3. Link 55 under 8: a B1 of 2 nodes, carried to degree 1.

    Link 55 under 8.

  4. Degree 1: 2 trees, rooted at 12, 8. Two of a kind: link them, and the result is a B2 that joins the next degree.

    Degree 1: 2 trees.

  5. Link 12 under 8: a B2 of 4 nodes, carried to degree 2.

    Link 12 under 8.

  6. Degree 2: 2 trees, rooted at 10, 8. Two of a kind: link them, and the result is a B3 that joins the next degree.

    Degree 2: 2 trees.

  7. Link 10 under 8: a B3 of 8 nodes, carried to degree 3.

    Link 10 under 8.

  8. Degree 3: 1 tree, rooted at 8. Nothing to link. It stays.

    Degree 3: 1 trees.

  9. Merged: 8 keys as B3, which is 8 in binary, 1000, after 3 links. The merge touched only the root lists, O(log n) trees, and never looked inside a tree: that is the operation a binary heap cannot do in less than O(n).

    Merged into 1 trees.

The code

Binomial and Fibonacci Heaps, in Python

def link(a, b):                                                   # two trees of equal degree become one
    small, big = (a, b) if a.key <= b.key else (b, a)
    small.children.append(big); big.parent = small; return small  # degree goes up by one
def binomial_merge(x, y):                                         # roots sorted by degree, like binary digits
    roots = sorted(x + y, key=lambda n: n.degree)
    i = 0
    while i + 1 < len(roots):
        if roots[i].degree != roots[i + 1].degree:
            i += 1; continue
        if i + 2 < len(roots) and roots[i + 2].degree == roots[i].degree:  # three: leave one
            i += 1; continue
        roots[i] = link(roots.pop(i + 1), roots[i])               # two of a degree: link, a carry
    return roots
def binomial_insert(heap, key):
    return binomial_merge(heap, [Node(key)])

def fib_extract_min(h):                                           # the lazy heap pays here
    min_node = min(h.roots, key=lambda n: n.key); h.roots.remove(min_node); h.roots += min_node.children
    by_degree = {}
    for r in list(h.roots):                                       # consolidate: one tree per degree
        t = r
        while by_degree.get(t.degree) is not None: t = link(t, by_degree.pop(t.degree))
        by_degree[t.degree] = t
    h.roots = list(by_degree.values()); return min_node.key
def fib_decrease_key(h, x, k):
    x.key = k
    y = x.parent
    if y is None: return
    if x.key >= y.key: return                                     # heap order intact
    cut(h, x); p = y
    while p.marked:                                               # cascading cut: a marked parent goes too
        cut(h, p); p = p.parent
        if p is None: return
    if p.parent is not None: p.marked = True                      # the first unmarked ancestor takes the mark

Binomial and Fibonacci Heaps, in JavaScript

function link(a, b) {                                           // two trees of equal degree become one
  const [small, big] = a.key <= b.key ? [a, b] : [b, a];
  small.children.push(big); big.parent = small; return small;   // degree goes up by one
}
function binomialMerge(x, y) {                                  // roots sorted by degree, like binary digits
  const roots = [...x, ...y].sort((m, n) => m.degree - n.degree);
  let i = 0;
  while (i + 1 < roots.length) {
    if (roots[i].degree !== roots[i + 1].degree) { i++; continue; }
    if (i + 2 < roots.length && roots[i + 2].degree === roots[i].degree) { i++; continue; }   // three: leave one
    roots[i] = link(roots.splice(i + 1, 1)[0], roots[i]);       // two of a degree: link, a carry
  }
  return roots;
}
function binomialInsert(heap, key) { return binomialMerge(heap, [new Node(key)]); }

function fibExtractMin(h) {                                     // the lazy heap pays here
  const min = h.roots.reduce((m, n) => (n.key < m.key ? n : m));
  h.roots.splice(h.roots.indexOf(min), 1); h.roots.push(...min.children);
  const byDegree = new Map();
  for (const r of [...h.roots]) {                               // consolidate: one tree per degree
    let t = r;
    while (byDegree.has(t.degree)) {
      const other = byDegree.get(t.degree); byDegree.delete(t.degree); t = link(t, other);
    }
    byDegree.set(t.degree, t);
  }
  h.roots = [...byDegree.values()]; return min.key;
}
function fibDecreaseKey(h, x, k) {
  x.key = k;
  const y = x.parent;
  if (y === null) return;
  if (x.key >= y.key) return;                                   // heap order intact
  cut(h, x); let p = y;
  while (p.marked) {                                            // cascading cut: a marked parent goes too
    cut(h, p); p = p.parent;
    if (p === null) return;
  }
  if (p.parent !== null) p.marked = true;                       // the first unmarked ancestor takes the mark
}

Binomial and Fibonacci Heaps, in Kotlin

fun link(a: Node, b: Node): Node {                           // two trees of equal degree become one
    val (small, big) = if (a.key <= b.key) a to b else b to a
    small.children += big; big.parent = small; return small   // degree goes up by one
}
fun binomialMerge(x: List<Node>, y: List<Node>): List<Node> {  // roots sorted by degree, like binary digits
    val roots = (x + y).sortedBy { it.degree }.toMutableList()
    var i = 0
    while (i + 1 < roots.size) {
        if (roots[i].degree != roots[i + 1].degree) { i++; continue }
        if (i + 2 < roots.size && roots[i + 2].degree == roots[i].degree) { i++; continue }   // three: leave one
        roots[i] = link(roots.removeAt(i + 1), roots[i])        // two of a degree: link, a carry
    }
    return roots
}
fun binomialInsert(heap: List<Node>, key: Int) = binomialMerge(heap, listOf(Node(key)))

fun fibExtractMin(h: FibHeap): Int {                           // the lazy heap pays here
    val min = h.roots.minBy { it.key }; h.roots.remove(min); h.roots += min.children
    val byDegree = HashMap<Int, Node>()
    for (r in h.roots.toList()) {                                // consolidate: one tree per degree
        var t = r
        while (byDegree[t.degree] != null) { t = link(t, byDegree.remove(t.degree)!!) }
        byDegree[t.degree] = t
    }
    h.roots = byDegree.values.toMutableList(); return min.key
}
fun fibDecreaseKey(h: FibHeap, x: Node, k: Int) {
    x.key = k
    var y = x.parent ?: return
    if (x.key >= y.key) return                                 // heap order intact
    cut(h, x); var p = y
    while (p.marked) { cut(h, p); p = p.parent ?: return }      // cascading cut: a marked parent goes too
    if (p.parent != null) p.marked = true                       // the first unmarked ancestor takes the mark
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • Binomial heap: at most one tree per degree, so n keys make at most log n + 1 trees and merge is binary addition over the root lists.
  • Fibonacci heap: stay lazy. Extract-min consolidates by linking equal degrees, which is where inserts finally pay.
  • Decrease-key cuts the node to the root list. A parent that loses a second child is cut too, which keeps trees bushy.

Where this is used

Boost.Heap's mergeable and mutable queuesC++ libraries

std::priority_queue is a binary heap over a vector, which rules out two things outright: merging two queues cheaply, and changing the priority of an element already inside, because every sift moves elements to different array slots and invalidates anything you were holding. Boost.Heap ships binomial_heap, fibonacci_heap, pairing_heap and skew_heap for precisely those gaps - push returns a handle to a node that never moves, so decrease() reaches the element directly, and merge() folds one heap's node structure into the other instead of popping and re-pushing every element.

join() and modify() in libstdc++ policy-based data structuresDeveloper tools

GCC ships __gnu_pbds::priority_queue next to the standard one, parameterised by pairing_heap_tag, binomial_heap_tag, rc_binomial_heap_tag, thin_heap_tag or binary_heap_tag. The thin heap is a Fibonacci heap variant that the manual credits with the same amortized bounds and better worst-case ones. Its push returns a point_iterator, and that handle is what makes modify() and erase() expressible at all, while join() merges one queue into the other in place rather than popping and re-pushing. It is the usual answer when a Dijkstra or A* wants a real decrease-key instead of pushing duplicate entries and discarding stale pops.

The O(E + V log V) bound for Dijkstra and PrimGraph algorithms

Fredman and Tarjan built the Fibonacci heap around one accounting observation: Dijkstra performs up to E decrease-keys but only V extract-mins, so moving the log factor off decrease-key and onto extract-min turns O(E log V) into O(E + V log V), which is a real win once the graph is dense. The honest footnote is that the constants rarely pay off, so production routing and MST code tends to run a 4-ary or pairing heap and the Fibonacci bound survives mainly as the benchmark everything else is measured against.

Purely functional priority queuesFunctional programming

Haskell's heaps package implements Brodal and Okasaki's bootstrapped skew-binomial heaps, a binomial-heap descendant whose union is O(1). Linking is what makes this work without mutation: it allocates one new node pointing at two existing subtrees, so both input heaps stay valid and the new one shares nearly all of their structure. An array-backed binary heap has no equivalent move, since keeping an old version means copying the whole array.

Why it works this way

Why the trees are powers of two, and why n inserts cost O(n)

The sizes are forced, not chosen: linking two trees of degree k - 1 gives one of degree k, so a binomial tree of degree k holds exactly 2 to the k nodes and there is no other shape available. That is what makes the root list the binary representation of n, and it makes an insert an increment - it carries only while the low digits are ones. Most increments carry once or not at all, and since every link removes one tree, n inserts into an empty heap do exactly n minus popcount(n) links - fewer than n in total - so filling it with n keys costs O(n) even though a single insert can cost log n. It is the amortized binary counter argument, unchanged.

Why a Fibonacci heap bothers to mark nodes

Consolidation is only cheap because a root's degree stays O(log n), and that bound survives only if a tree of degree k really contains many nodes. Cuts are the threat: strip children away freely and you end up with high-degree roots holding almost nothing, and extract-min starts scanning a long array of degrees for nothing. The mark bit is the bookkeeping that caps the damage at one lost child per node, and from that cap you can prove a node of degree k holds at least F(k + 2) nodes, roughly phi to the k, which pins the maximum degree at O(log n). That lower bound is where the name comes from and is the entire reason decrease-key does not destroy extract-min.

Amortized is not worst case, and the constants are real

Every O(1) here is an average over a sequence, not a promise about one call. Do a million lazy inserts and the next extract-min walks a million-node root list before it consolidates, so a single operation can take O(n) while the sequence stays within budget. That rules the structure out of hard real-time work, and it is only half the problem: four pointers plus a mark bit per node and constant pointer chasing mean a pairing heap, which gives up the proven O(1) decrease-key, usually wins on a real machine anyway.

decrease-key needs a handle, not a key

Nothing in a heap is searchable - finding a node by its value is an O(n) scan of the forest - so the caller must have kept the node reference that insert handed back. This is why Dijkstra implementations carry a vertex-to-node map beside the heap, and why a heap API that only takes values cannot offer decrease-key at all. Deleting and reinserting is not a substitute: an arbitrary delete is itself decrease-key to minus infinity followed by extract-min, which costs O(log n) amortized and throws away the exact bound you wanted.

Read more

Next up