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

Inserting 5 keys into a binomial heap.heap

Insert 40, 25, 60, 15, 50 into an empty binomial heap. A binomial heap holds at most one tree of each degree: B0 is a single node, B1 two nodes, B2 four, and so on, so the tree sizes present spell n in binary. Inserting a key adds a B0 and then behaves exactly like adding 1 to a binary number: two trees of the same degree link into one of the next degree, and the carry can run on.

Check your understanding

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

  1. The heap holds none and a new B0 arrives. How many links happen?

    • 0
    • 1

    Answer: 0. Count the degrees already present from 0 upward without a gap: each one is a carry.

  2. The heap holds B0 and a new B0 arrives. How many links happen?

    • 0
    • 1
    • 2

    Answer: 1. Count the degrees already present from 0 upward without a gap: each one is a carry.

  3. The heap holds B1 and a new B0 arrives. How many links happen?

    • 0
    • 1

    Answer: 0. Count the degrees already present from 0 upward without a gap: each one is a carry.

  4. The heap holds B0, B1 and a new B0 arrives. How many links happen?

    • 0
    • 2
    • 3

    Answer: 2. Count the degrees already present from 0 upward without a gap: each one is a carry.

  5. The heap holds B2 and a new B0 arrives. How many links happen?

    • 0
    • 1

    Answer: 0. Count the degrees already present from 0 upward without a gap: each one is a carry.

How it runs, step by step

  1. Insert 40, 25, 60, 15, 50 into an empty binomial heap. A binomial heap holds at most one tree of each degree: B0 is a single node, B1 two nodes, B2 four, and so on, so the tree sizes present spell n in binary. Inserting a key adds a B0 and then behaves exactly like adding 1 to a binary number: two trees of the same degree link into one of the next degree, and the carry can run on.

    Inserting 5 keys into a binomial heap.

  2. Insert 40 as a new B0, key 1 of 5. The forest holds none: no B0 yet, so the new tree simply joins the root list.

    Insert 40: 0 links.

  3. 1 keys held as B0: 1 in binary is 1, one bit per tree present. The minimum is among the 1 root.

    1 trees: B0.

  4. Insert 25 as a new B0, key 2 of 5. The forest holds B0, so the new B0 meets another B0: they link into a B1, and that links on for as long as the next degree is occupied, 1 1 link in all, like 1 carries in binary addition.

    Insert 25: 1 links.

  5. Two trees of degree 0: 25 and 40. The smaller key stays on top and the other tree hangs under it as its newest child, giving a B1 of 2 nodes.

    Link 40 under 25.

  6. 2 keys held as B1: 2 in binary is 10, one bit per tree present. The minimum is among the 1 root.

    1 trees: B1.

  7. Insert 60 as a new B0, key 3 of 5. The forest holds B1: no B0 yet, so the new tree simply joins the root list.

    Insert 60: 0 links.

  8. 3 keys held as B0, B1: 3 in binary is 11, one bit per tree present. The minimum is among the 2 roots.

    2 trees: B0, B1.

  9. Insert 15 as a new B0, key 4 of 5. The forest holds B0, B1, so the new B0 meets another B0: they link into a B1, and that links on for as long as the next degree is occupied, 2 2 links in all, like 2 carries in binary addition.

    Insert 15: 2 links.

  10. Two trees of degree 0: 15 and 60. The smaller key stays on top and the other tree hangs under it as its newest child, giving a B1 of 2 nodes.

    Link 60 under 15.

  11. Two trees of degree 1: 15 and 25. The smaller key stays on top and the other tree hangs under it as its newest child, giving a B2 of 4 nodes.

    Link 25 under 15.

  12. 4 keys held as B2: 4 in binary is 100, one bit per tree present. The minimum is among the 1 root.

    1 trees: B2.

  13. Insert 50 as a new B0, key 5 of 5. The forest holds B2: no B0 yet, so the new tree simply joins the root list.

    Insert 50: 0 links.

  14. 5 keys held as B0, B2: 5 in binary is 101, one bit per tree present. The minimum is among the 2 roots.

    2 trees: B0, B2.

  15. 5 keys in 2 trees, B0, B2, after 3 links. A binomial heap of n keys has at most log2(n) + 1 trees, so every operation, insert, merge, extract-min, is O(log n), and merging two whole heaps is just the same binary addition over both root lists at once.

    2 trees after 3 links.

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