Cairn
data structures · tenth Node-Linked Trees entry · O(1) amortized insert / decrease-key · O(log n) amortized extract-min

↩ back to Node-Linked Trees

Fibonacci Heap

The site's tenth node-linked trees entry, and a forward reference Johnson's Algorithm's own Complexity section has named twice — "a Fibonacci heap tightens this to the more commonly cited" bound — with nowhere to link to until now. A binary heap gives every operation a hard O(log n) ceiling by keeping one strict shape rule. A Fibonacci heap throws that discipline out: it lets itself become a messy forest of trees, does almost no housekeeping on insert, and only pays for the mess when it has no choice — extractMin. The payoff is decrease-key, the one operation a binary heap can't do cheaply at all: amortized O(1), not O(log n). That single difference is why Dijkstra, Prim, and Johnson's algorithm all get a tighter textbook bound when the citation says "with a Fibonacci heap."

Try it

Insert a few values — each one just becomes its own single-node tree in the root list, no comparisons at all. Extract Min removes the current minimum, promotes its children straight into the root list, and then consolidates: repeatedly merges any two root trees that share the same degree (child count) until every remaining root has a distinct degree. Click any node to select it, then Decrease Key to lower it below its parent — watch it get cut loose into the root list, and watch the marked dashed outline propagate up the tree if a cascading cut fires.

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

Core operations

Why it works: lazy now, one bill later

A binary heap does a little work on every insert (sift up) to keep its shape invariant true at all times. A Fibonacci heap does the opposite: insert does nothing but append, so after a run of n inserts with zero extractions, the root list is just n separate single-node trees — no structure at all yet. All of that deferred work comes due at once on the next extractMin, whose consolidation pass has to fold every one of those roots down by repeatedly merging same-degree pairs. One such call can genuinely cost O(n) — see the measured numbers in Pitfalls — but it's the only call that ever pays for those n free inserts, so spread across the whole sequence the average (amortized) cost per operation is still O(log n). This is exactly the same kind of accounting Dynamic Array's doubling resize uses: individual operations can spike, but no adversary can make every operation in a long sequence expensive at once.

Why degree-merging bounds the tree count. After consolidation, no two roots share a degree — with root degrees drawn from {0, 1, 2, ...}, that alone caps the final root count at roughly log₂ n. That's also where the structure's name comes from: a node of degree k can be shown (by induction, tracking the minimum possible size at each degree) to root a subtree of at least F(k+2) nodes, the (k+2)-th Fibonacci number — which grows fast enough that the maximum possible degree of any node in an n-node heap is O(log_φ n), φ the golden ratio. Every "amortized O(log n)" claim on this page is that bound, not a looser one.

Why cascading cut exists. That Fibonacci-number size bound assumes a node's subtree only ever grows, never quietly loses pieces — but decreaseKey's cut operation does exactly that, lopping a whole child subtree off and dropping it into the root list. Left unchecked, a single node could be cut down to degree 0 one child at a time, no matter how large a subtree it used to certify. The fix is the marked bit: the first time a node loses a child, it gets marked (a debt: "you've lost one, next time you're cut too"). If it loses a second child while still marked, it's cut as well — and the cut cascades up to check its own parent, and so on, until it reaches a node that wasn't marked yet (which gets marked instead and the cascade stops) or reaches a root (roots are never marked — there's no parent above a root to owe a debt to). This caps how far any single subtree can shrink before the structure forces it back into the root list where it can start earning size again, which is exactly what keeps the degree bound from the previous paragraph honest.

Reference implementation

class FibNode {
  constructor(key) {
    this.key = key;
    this.children = [];
    this.parent = null;
    this.marked = false;
  }
}

class FibHeap {
  #roots = [];
  #min = null;

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

  insert(key) {
    const node = new FibNode(key);
    this.#roots.push(node);
    if (this.#min === null || node.key < this.#min.key) this.#min = node;
    return node;
  }

  #consolidate() {
    const byDegree = new Map();
    for (const r0 of this.#roots) {
      let x = r0;
      while (true) {
        const d = x.children.length;
        if (!byDegree.has(d)) { byDegree.set(d, x); break; }
        let y = byDegree.get(d);
        if (y.key < x.key) [x, y] = [y, x];   // x keeps the smaller key, absorbs y
        byDegree.delete(d);
        y.parent = x; y.marked = false;
        x.children.push(y);
      }
    }
    this.#roots = [...byDegree.values()];
    this.#min = null;
    for (const r of this.#roots) if (this.#min === null || r.key < this.#min.key) this.#min = r;
  }

  extractMin() {
    const z = this.#min;
    if (!z) return null;
    this.#roots = this.#roots.filter((r) => r !== z);
    for (const c of z.children) { c.parent = null; c.marked = false; this.#roots.push(c); }
    if (this.#roots.length === 0) this.#min = null;
    else this.#consolidate();
    return z.key;
  }

  #cut(node, parent) {
    parent.children = parent.children.filter((c) => c !== node);
    node.parent = null;
    node.marked = false;
    this.#roots.push(node);
  }

  #cascadingCut(node) {
    const parent = node.parent;
    if (!parent) return;               // roots never cascade further
    if (!node.marked) { node.marked = true; return; }
    this.#cut(node, parent);
    this.#cascadingCut(parent);
  }

  decreaseKey(node, newKey) {
    if (newKey >= node.key) return false;
    node.key = newKey;
    const parent = node.parent;
    if (parent && node.key < parent.key) {
      this.#cut(node, parent);
      this.#cascadingCut(parent);
    }
    if (this.#min === null || node.key < this.#min.key) this.#min = node;
    return true;
  }
}

Verified with a seeded, reproducible stress harness (Node's own Math.random replaced by a small seeded generator so any failure replays exactly): 10,000 randomized trials of interleaved insert / extract-min / decrease-key sequences, keys drawn from a small range on purpose to force frequent duplicate keys, checking after every single operation that (1) the min-heap property holds everywhere in the forest — every node's key is ≤ every one of its children's, (2) every non-root node's parent pointer actually points at its real parent and every root's is null, (3) no root is ever marked, (4) the min pointer's key matches the true minimum across all roots, and (5) the full multiset of live keys in the forest exactly matches an independent linear-scan oracle's — catching not just wrong answers but silent loss or duplication of a node. Zero failures across 10,000 trials (~700,000 operations). The harness itself was self-tested first against two deliberately broken copies of the reference model (one that forgets to null a promoted child's parent pointer, one that forgets to refresh the min pointer after a decrease-key) — both caught immediately, confirming the checks have real teeth before trusting a clean run to mean anything. A first draft of the test oracle produced spurious mismatches on duplicate keys by assuming extractMin must always remove whichever duplicate was inserted first; a real Fibonacci heap makes no such promise; fixed by comparing keys and the multiset of survivors, not a specific node identity, on ties.

The shipped demo above runs its own copy of this logic (adapted to log each step instead of returning silently), not the reference model directly — so it needed its own separate verification, extracting the actual functions out of this page's own <script> via Node's vm module and re-running an equivalent 10,000-trial harness against them (with the multiset check re-derived from the live structure itself each step, since the shipped extractMin intentionally returns a plain {key, ...} summary for the log line, not a node identity to track). That re-run caught a real bug the reference-model testing above couldn't have: the shipped cascadingCut had node and parent transposed — it was marking and cutting the wrong one of the pair, a transcription slip from re-typing the already-verified logic a second time for the demo rather than sharing one implementation. Every correctness check still ran clean with the bug in place except the one that matters (roots turned up wrongly marked), which is exactly the "a correct reference model and a correct-looking shipped demo are still two different things to verify" lesson this site has hit before — re-run the stress test against the extracted shipped code, not just the standalone model it was translated from. Fixed and reconfirmed clean across another 10,000 trials against the corrected shipped functions, and the self-test itself was re-run against the broken version first to confirm the harness actually catches it (11 failures, all "root is marked") before trusting the clean result on the fix.

Pitfalls

A single operation can still be slow — the guarantee is only about the average. Insert n values with zero extractions in between, then call extractMin exactly once: that one call has to consolidate every root the lazy inserts left behind. Directly instrumenting the reference model's consolidation pass confirms the shape of this cost rather than just asserting it: after n = 10, 100, 1,000, and 10,000 plain inserts, a single extractMin() call performs 7, 95, 991, and 9,991 root-merge operations respectively — essentially n − 1 every time, not log n — while still collapsing the forest down to only 2, 4, 8, and 8 surviving trees. The amortized O(log n) bound is a statement about a long sequence's average, not a promise that any individual call is cheap; a system with a real-time deadline on every single call still can't use this structure safely no matter how good the amortized bound looks on paper.

The constant factors are real, and this rarely wins in practice. Every node carries a parent pointer, a children list, and a marked bit that a binary heap's flat array simply doesn't need, and consolidation means pointer-chasing through a scattered forest instead of scanning one contiguous array. Unless a workload does enough decrease-key calls for the amortized O(1) bound to matter — dense graph algorithms with many edge relaxations being the classic case — a plain binary heap's better cache behavior and lower overhead usually wins despite the worse asymptotic bound. This is exactly why Dijkstra's and Prim's own demos on this site use a binary heap (or a plain linear scan, for clarity), not this page's structure, even though both pages cite the Fibonacci heap bound in their own Complexity sections as the theoretical ceiling.

Skipping cascading cut breaks the degree bound, not the returned values. Every invariant this page's stress harness checks — heap order, parent pointers, the min pointer, the live multiset — stays true even in a version that marks nodes but never re-cuts them, because cascading cut exists purely to bound how large a node's degree can grow relative to its current subtree size, not to keep any single answer correct. A correctness test alone would never catch a broken or missing cascading cut; only an argument (or a measurement) about degree growth under repeated decrease-key calls would. Worth remembering as its own category: an amortized-complexity invariant and a correctness invariant are different things to verify, and a green correctness suite says nothing about whether the complexity claim still holds.

Where Fibonacci heaps show up

Complexity

Time: insert is O(1), genuinely worst-case, not just amortized. peek is O(1). decreaseKey is O(1) amortized — a single call can cascade all the way up a chain of marked ancestors, but the marking scheme guarantees that cost is paid back by the sequence of earlier operations that set those marks (see Why it works). extractMin is O(log n) amortized — a single call's real cost is bounded by the number of roots plus the maximum degree, both O(log n) only once amortized across the inserts that built them up (see Pitfalls for how large one call alone can get). Space: O(n) — one node per element, each carrying a parent pointer, a children list, and a marked bit; strictly more per-node overhead than a binary heap's flat array.

This site's guide, Choosing a Search Tree, groups this entry with Pairing, Leftist, Skew, and Binomial Heap as a mergeable priority queue rather than an ordered set — none of the five answers a general search for an arbitrary key. Among them, it's the one that earns a fully proven O(1) amortized decrease-key, at the cost of marked bits and cascading cuts the other four don't carry.