Fibonacci Heaps

By the end of this lesson you will be able to explain why a Fibonacci heap is a lazy, forest-of-trees version of the binary heap, trace every one of its operations (makeHeap, insert, minimum, union, extractMin with consolidate, decreaseKey with cut and cascadingCut, delete) row by row, and use the potential method to see WHY most of these operations cost O(1) amortized even though a single call can occasionally do a lot of work — the same trick that makes Dijkstra's algorithm and Prim's algorithm asymptotically faster on dense graphs.

1. Structure: a forest of trees, marks, and the potential Φ

A binary heap is like a single, always-tidy filing cabinet: every time you add or remove a folder you immediately re-sort everything so the cabinet is always perfectly organised. A Fibonacci heap is the opposite personality: it is a messy desk with several small piles of papers (trees) lying around. Adding a new paper (INSERT) just drops it as a brand-new one-paper pile — no tidying at all. Only when you actually need "give me the most urgent paper" (extractMin) does the desk get tidied up, and even then only just enough to keep things from getting out of hand later. This laziness is exactly why most operations are so cheap.

A Fibonacci heap H is a collection of min-heap-ordered rooted trees: for every node x other than a root, key(x) ≥ key(parent(x)) (the mirror image of a max-heap's rule: "smallest on top" instead of "largest on top"). The trees' roots are strung together in a doubly linked root list, and H.min is a pointer straight at whichever root currently holds the smallest key. H.n counts the total number of nodes across every tree.

Every node x carries four small pieces of record-keeping:

x.parent — the node directly above it, or null if x is a root.
x.children — the list of x's children (a production version keeps one child pointer plus a circular doubly linked sibling list; on this page we draw it as a plain ordered list, which behaves identically for every purpose we care about here).
x.degree — how many children x currently has.
x.mark — a single TRUE/FALSE flag meaning "has x lost a child since the last time x itself became a child of someone else?" A brand-new node, or one that has just become a child, always starts unmarked.

The mark is the heap's entire "memory" of recent surgery, and it exists for exactly one purpose, explained fully in Section 7: it lets decreaseKey decide, in O(1) time, whether cutting a node loose should stop immediately or should keep cascading upward.

A production implementation gives every node a circular doubly linked sibling list (via left/right pointers) so that splicing a node in or out of a list — root list or child list — is O(1) no matter how long the list is, with no shifting. This page's JavaScript simulation stores children and roots as plain ordered lists instead, because that is far easier to read on a teaching page and produces exactly the same sequence of links, cuts and degrees — the circular-list plumbing is a constant-factor implementation detail, not part of the algorithm's logic. The Dart implementation later in this lesson makes the same simplification, using List<FibNode<T>> for both the root list and each node's children.

The potential function. To explain why a single expensive operation is fine as long as cheap operations "pre-pay" for it, we define, for any Fibonacci heap H:

Φ(H) = t(H) + 2·m(H)

where t(H) is the number of trees currently in the root list and m(H) is the number of currently marked nodes anywhere in H. Think of Φ(H) as "banked-up messiness credit": every tree in the root list is one unit of stored-up tidying work, and every marked node is worth two units (one to pay for cutting it later, one to pay for the new tree it will create when it's cut). A brand-new empty heap has t=0, m=0, so Φ=0, and Φ can never go negative — both conditions the potential method requires to give a valid upper bound on total real cost.

The same potential as Dart on the lesson’s FibonacciHeap: t(H) is the length of the root list, m(H) counts marked nodes by walking every tree, and the amortized cost of an operation is its actual cost plus ΔΦ. The helper functions at the bottom of the panel (findNode, heapMaxDegree) are used by the checks later in the lesson.

A very common mix-up: Φ is not a cost paid by any single operation — it is a snapshot of the whole heap's current "shape debt". The amortized cost of an operation is defined as actual cost + ΔΦ (potential AFTER minus potential BEFORE). When ΔΦ is negative (the heap gets tidier), the amortized cost can be much smaller than the actual work done — that is precisely what happens inside CONSOLIDATE.

A Fibonacci heap is a forest of min-heap-ordered trees linked in a root list, with H.min always pointing at the smallest root. Each node tracks its parent, children, degree, and a mark bit. Φ(H) = t(H) + 2·m(H) banks up "messiness credit" from loose trees and marked nodes — the accounting tool every analysis in this lesson is built on.

2. make heap and MINIMUM

makeHeap is just clearing the desk entirely — an empty desk has no piles and nothing marked. MINIMUM is glancing at the one sticky note on your monitor that always says "the most urgent pile is over there" — you never have to search the piles because that note is kept up to date by every other operation.

makeHeap() allocates an empty heap: H.n ← 0, H.min ← null, no trees. minimum() simply returns H.min — because every other operation always keeps this pointer correct, MINIMUM never has to walk any tree.

Input size → what is feasible. Any n that fits in memory (10⁶ nodes ≈ 10² MB of Dart objects): makeHeap sets three fields and MINIMUM reads one pointer, so both are Θ(1) whether n = 1 or n = 10⁶.

Beginners sometimes assume MINIMUM has to compare all the root keys, the way you'd find the max of an unsorted array. It does not — H.min is a single pointer maintained incrementally by INSERT, UNION, CONSOLIDATE and decreaseKey, so reading it is always O(1), regardless of how many trees or nodes the heap holds.

makeHeap: Θ(1), creates an empty heap with Φ=0. MINIMUM: Θ(1), a direct pointer read — no traversal, ever.

3. INSERT

Dropping a brand-new single sheet of paper onto the desk as its own tiny pile. You don't reorganise anything else — you just place it down, and if it happens to be more urgent than the current "most urgent" sticky note, you update that note.

insert(key) is animated below with its 9 numbered rows in the code panel:

The ΔΦ = +1 claim, measured on a real heap:

Input size → what is feasible. n = 10⁶ INSERTs → 10⁶ constant-time steps, while a binary heap spends about 10⁶ · 20 = 2·10⁷ sift steps; the Dart class allocates one FibNode (with its own child set) per key, so keep n ≲ 10⁶.

Running-time analysis. Every line of INSERT is O(1) — field initialisation, one splice into a doubly linked list, and one comparison. The amortized cost adds ΔΦ: INSERT always creates exactly one new tree and never changes any mark, so ΔΦ = (t+1) + 2m − (t + 2m) = +1. Amortized cost = actual O(1) + ΔΦ·(a constant unit cost) = O(1) — dramatically better than a binary heap's Θ(lg n) siftUp.

INSERT does not restore any global order among the roots — right after several INSERTs, the root list can be a long line of completely unrelated single-node trees. That is intentional laziness, not a bug: the tidying cost is only paid later, inside CONSOLIDATE, and only once per extractMin.

INSERT: Θ(1) actual and Θ(1) amortized. It only ever adds one new one-node tree to the root list and fixes H.min if needed — no merging happens here.

4. UNION

Pushing two separate desks together so their piles are now all on one big desk. You don't restack anything — you just note which desk's "most urgent" sticky note wins.

union(H1, H2) destroys H1 and H2 and returns a new heap containing everything from both (in practice you would just reuse one of the two heap objects):

The Dart union above copies the roots of both heaps (hash sets). The true Θ(1) comes from keeping each root list as a circular doubly linked list, where joining two lists is four pointer writes, however long they are:

Input size → what is feasible. Two heaps of 10⁵ nodes each: the circular-list UNION is 4 pointer writes, a binary-heap merge moves Θ(n) = 2·10⁵ keys, and this lesson’s hash-set UNION copies every root (constant only when the root lists are short).

Running-time analysis. Concatenating two doubly linked root lists is O(1) regardless of their sizes — you only touch a handful of pointers at the two splice points, never walk either list. ΔΦ is exactly the sum of the two input potentials minus nothing extra, so UNION is O(1) actual and O(1) amortized. Compare this with a binary heap: merging two n/2-element arrays into one heap needs Θ(n) just to rebuild the array (buildMaxHeap), which is the single biggest asymptotic win Fibonacci heaps offer over binary heaps for merging.

UNION: Θ(1) actual and amortized — just pointer-splice two root lists and keep the smaller of the two minimums. A binary heap needs Θ(n) for the same job.

5. extract min

This is the one moment the desk actually gets tidied. You grab the most urgent pile (H.min), scatter every paper that was resting on top of it back onto the desk as its own new pile, throw away the folder that held them, and only then do you spend a moment merging same-sized piles together so the desk doesn't get out of control (that merging step is CONSOLIDATE, covered in full in Section 6).

Here is extractMin(), row by row:

Input size → what is feasible. n = 10⁵ nodes: one call may cost Θ(n) = 10⁵ steps right after many INSERTs, but n extractMin calls together cost O(n lg n) ≈ 1.7·10⁶ steps because D(n) ≤ ⌊log_φ 10⁵⌋ = 23.

Running-time analysis (preview — full derivation with CONSOLIDATE in Section 6). Rows 1–9 and 11 do O(z.degree) work moving z's children into the root list, which is O(D(n)) since no node's degree ever exceeds D(n) (bounded in Section 9). Row 10's call to consolidate is where nearly all the real work — and nearly all of the potential drop — happens; the whole call is O(D(n)) amortized, i.e. O(lg n) amortized overall, even though the actual work in a single call can be as large as Θ(n) in the worst case (many single-node trees all consolidating at once).

A single extractMin call can legitimately take a long time — it is only the amortized (averaged over a whole sequence of operations) cost that is O(lg n). This is exactly why Fibonacci heaps are attractive for algorithms like Dijkstra that call decreaseKey very often but extractMin only once per vertex: the expensive tidying is rare and gets paid for by all the cheap decreaseKey calls and INSERTs that came before it.

extractMin: O(lg n) amortized (O(D(n) + t(H)) actual, with D(n) = O(lg n)). It promotes the removed root's children to the root list, then hands the tidying job to CONSOLIDATE.

6. CONSOLIDATE (the linking engine behind extract min)

Imagine sorting piles by how many papers are in each pile (that count is a tree's degree) using a row of labelled boxes A[0], A[1], A[2], … — one box per possible pile-size. You walk the piles one by one: if box A[d] is empty, you just set that pile down in it. If A[d] already has a pile in it, the two piles of matching size must be combined into one bigger pile (the one with the smaller top page becomes the "boss" on top), and now you try to place that bigger pile in A[d+1] — repeating the merge for as long as there's a collision. At the very end, every box that holds a pile becomes one root of the tidied desk.

This is exactly consolidate()'s job. It relies on one small helper, link(y, x), which makes root y a child of root x (only ever called when key(x) ≤ key(y), so the heap-order property is preserved):

And here is consolidate() itself — D(H.n) is the largest possible node degree for a heap of H.n nodes (bounded in Section 9), so the array A needs that many slots plus one for degree 0:

Running-time analysis (the heart of the lesson). Let D = D(H.n). The size of the root list CONSOLIDATE starts with is at most D(n) + t(H) − 1 (every child promoted by extractMin plus the pre-existing roots, minus the removed minimum). Every iteration of the inner while loop performs one link and removes one tree from the root list, so the total number of link operations across the WHOLE call is at most the starting root-list size. Actual cost = O(D(n) + t(H)).

Now the potential trick: before CONSOLIDATE, Φ = t(H) + 2m(H). Afterwards, the root list has at most D(n) + 1 trees (one per degree slot, and CONSOLIDATE never creates a new mark), so Φ' ≤ (D(n)+1) + 2m(H). Amortized cost = actual + ΔΦ ≤ O(D(n) + t(H)) + [(D(n)+1) + 2m(H)] − [t(H) + 2m(H)] = O(D(n)) − t(H) + O(1) = O(D(n)) — the t(H) terms CANCEL, because scaling one unit of potential to be worth "enough currency" makes every tree CONSOLIDATE destroys pay for the work of destroying it. Since D(n) = O(lg n) (Section 9), CONSOLIDATE — and therefore extractMin — is O(lg n) amortized.

The same accounting in Dart: extractMinCost counts the roots CONSOLIDATE visits and the links it makes, takes ΔΦ from the real heap, and checks ĉ = actual + 2·ΔΦ ≤ 4·D(n) − 1 (the potential is scaled by 2 to pay for the hidden constant in O(D(n) + t(H)), exactly the “scale up the potential units” step of the proof):

Input size → what is feasible. t = 10⁵ roots (right after 10⁵ INSERTs): CONSOLIDATE does about 2·10⁵ steps once, then leaves at most D(n) + 1 = 24 trees; its array A needs only D(n) + 1 = 24 slots, not 10⁵.

A frequent beginner error when re-implementing CONSOLIDATE: forgetting that after linking, x's degree just increased, so you must recheck slot A[d+1] too — a single root can cascade through several merges in one call (that's exactly what the "worst case" animation above shows: one long chain of collisions). Forgetting the while, and only checking each slot once with an if, silently leaves duplicate-degree trees in the root list, breaking the O(lg n) degree bound this whole lesson is built on.

CONSOLIDATE repeatedly links same-degree roots (smaller key wins as parent) using a degree-indexed array A[0..D(n)], until every root has a unique degree. Actual cost O(D(n) + t(H)); amortized cost O(D(n)) = O(lg n) — the dropping tree count exactly pays for the linking work.

7. decrease key, CUT and cascading cut

Imagine a page halfway down a pile just became more urgent than the page directly above it. You can't leave it buried — you rip it out (CUT) and drop it onto the desk as the start of a brand-new pile. But there's a house rule: each pile is allowed to lose at most one buried page for free — the first time a page is ripped from underneath some page y, you stick a small flag ⚑ on y as a warning. If a SECOND page is ever ripped out from under an already-flagged y, then y itself gets ripped out too (its flag is removed, since it's now a fresh root) — and that ripping-out check repeats one level further up (cascadingCut). This rule is precisely what stops any one tree from silently growing tall and unbalanced from repeated cuts.

decreaseKey(x, k) lowers x's key to k (error if k is actually larger) and repairs heap order if needed:

decreaseKey's two helpers, shown here for reference (their effects are narrated inline above, at rows 5 and 6 of decreaseKey's own code, since they're always called from inside it on this page):

cut(x, y) — every cut the steps trigger, one row per line of code:

cascadingCut(y) — its own seven rows, one recursive call after another:

Running-time analysis (potential method). Let c = the number of cascadingCut calls made (each one is preceded by exactly one CUT: the initial CUT of x, then one cut per recursive call that finds a marked node). Each call does O(1) work excluding its own recursive call, so actual cost = O(c). Each cut moves one tree into the root list (t(H) goes up by c) and clears the mark of every node it cuts except possibly the very last one in the chain (which may end up freshly marked instead, if its own parent existed and it survived unmarked). So Δt = +c (c − 1 trees from cascading cuts plus the tree rooted at x) and Δm ≤ −(c−1) + 1 = −(c−2), giving ΔΦ \le c - 2(c-2) = 4 - c. Amortized cost = O(c) + (4 − c) = O(1) — every extra cascading cut costs O(1) more actual work but lowers Φ by 1 net (+1 tree, −2 for the cleared mark); after scaling the potential unit by a constant, that drop pays for the work, no matter how long the cascade runs.

And the cascade bound as code — c is read off as the growth of the root list, and ΔΦ ≤ 4 − c is what makes the amortized cost at most 5 however long the cascade:

Input size → what is feasible. E = 2·10⁵ decreaseKey calls (Dijkstra on 10⁵ vertices): at most 5 amortized steps each ≈ 10⁶ in total, versus ≈ lg V = 17 each (3.4·10⁶) with a binary heap.

It's tempting to think a long cascading-cut chain must be "slow" because it touches many nodes. The potential argument above shows the opposite: the LONGER the chain, the MORE marks it clears, which lowers Φ, which is exactly what keeps the amortized cost at O(1) regardless of chain length. This O(1) amortized decreaseKey — versus a binary heap's Θ(lg n) — is the single biggest reason Fibonacci heaps improve Dijkstra's and Prim's algorithms on dense graphs.

decreaseKey: O(1) amortized. A violated child is CUT to the root list; its old parent is marked if this is its first lost child, or itself CUT (and cascadingCut recurses) if it was already marked — the mark bit is what makes this whole chain O(1) amortized instead of unbounded.

8. DELETE

To throw a specific page away no matter how deep it's buried, the cheapest trick is: make it artificially the MOST urgent page in the world (decrease its key to negative infinity, which naturally rips it free and bubbles it to the top via the exact same CUT/cascadingCut machinery from Section 7), then just perform your normal "grab the most urgent page" operation, which is now guaranteed to grab exactly the page you wanted gone.

delete(x) is delightfully short — it is built entirely out of the two operations you already know:

Running-time analysis. decreaseKey(H, x, -∞) is O(1) amortized (Section 7) and extractMin is O(D(n)) = O(lg n) amortized (Sections 5–6). DELETE simply adds the two: O(1) + O(lg n) = O(lg n) amortized — identical to extractMin's bound, since that call dominates.

Input size → what is feasible. n = 10⁵ deletions of arbitrary nodes (handles in hand): O(lg n) amortized each ≈ 1.7·10⁶ steps plus 5 · 10⁵ for the decreaseKey calls; finding a node by key first would cost O(n) per delete.

DELETE(H,x) = decreaseKey(H,x,-∞) then extractMin(H). O(lg n) amortized — no separate machinery needed at all.

9. Bounding the maximum degree D(n)

Every analysis above leaned on "D(n) = O(lg n)" without proving it. The proof is a beautiful piece of reverse engineering: it shows that ANY node with degree k must secretly be hiding at least F_k+2 (a Fibonacci number!) descendants underneath it — and Fibonacci numbers grow so fast (like φ^k, the golden ratio to the k-th power) that a heap of only n nodes simply cannot contain a node whose degree is more than about log_φ n.

Child-degree rule. Let x be any node with x.degree = k, and let y₁, y₂, …, y_k be its children in the order they were linked to x (earliest first). Then y₁.degree ≥ 0 and, for i ≥ 2, y_i.degree ≥ i − 2.

Why: link only ever links two roots of EQUAL degree. So at the moment y_i was linked under x, x already had y₁, …, y_i−1 as children — i.e. x.degree was at least i−1 at that time — and linking requires y_i.degree to have equalled that same value then. Since that moment, y_i can have lost at most one child (a second loss would have triggered cascadingCut and removed it from under x entirely) — so today, y_i.degree ≥ (i−1) − 1 = i − 2.

The child-degree rule and the size bound as code — checked on every node of real heaps, and on the thinnest tree the lemma allows (a degree-k root whose children have degrees 0, 0, 1, 2, …, k − 2):

Minimum-size rule (consequence). Define size(x) = number of nodes in the subtree rooted at x. Using the child-degree rule and the Fibonacci recurrence F_k = F_k-1 + F_k-2, it is proved by induction that any degree-k node satisfies size(x) ≥ F_k+2, and separately (Fact B) that F_k+2 ≥ φ^k where φ = (1+√5)/2 ≈ 1.618 is the golden ratio.

Every formula of this section, computed: the Fibonacci numbers, φ, the minimum subtree sizes s_k from the child-degree rule, Facts A and B as boolean checks, the exact largest degree max{k : F_k+2 ≤ n}, and the closed bound ⌊log_φ n⌋ (plus the tighter ⌊lg n⌋ for heaps that never cut):

Input size → what is feasible. n = 10⁹ nodes → D(n) ≤ 43 (CONSOLIDATE needs at most 44 array slots); n = 10¹² → D(n) ≤ 57. Computing the bound takes a few dozen loop steps for any n that fits in a 64-bit int.

Degree bound. For a node x in an n-node Fibonacci heap, n ≥ size(x) ≥ φ^x.degree, so x.degree ≤ log_φ n. Therefore D(n) ≤ ⌊log_φ n⌋ = O(lg n) — this single inequality is what makes every O(lg n) bound in Sections 5–8 actually true.

Without decreaseKey and DELETE (i.e. using the heap only as a mergeable heap: makeHeap, INSERT, MINIMUM, extractMin, UNION), there is an even tighter bound, D(n) ≤ ⌊lg n&rfloor, because without cuts the trees end up looking exactly like binomial trees — a degree-k tree always has exactly 2^k nodes. It's specifically decreaseKey's cutting that can shrink a tree's node count below 2^k, which is exactly why the golden-ratio (not power-of-2) bound is needed once cuts are allowed.

D(n) ≤ ⌊log_φ n⌋ (so D(n) = O(lg n)), because every degree-k node is proven to hide at least a Fibonacci number of descendants, and Fibonacci numbers grow exponentially in the golden ratio φ. This bound is the reason extractMin, CONSOLIDATE and DELETE are all O(lg n) amortized.

10. Comparison with binary heaps & amortized-cost summary

This table compares a binary heap's worst-case bounds against a Fibonacci heap's amortized bounds:

Operation	Binary heap (worst-case)	Fibonacci heap (amortized)
`makeHeap` (`makeHeap`)	Θ(1)	Θ(1)
INSERT	Θ(lg n)	Θ(1)
MINIMUM	Θ(1)	Θ(1)
`extractMin`	Θ(lg n)	O(lg n)
UNION	Θ(n)	Θ(1)
`decreaseKey`	Θ(lg n)	Θ(1)
DELETE	Θ(lg n)	O(lg n)

Fibonacci heaps are most valuable when an algorithm calls decreaseKey far more often than extractMin — exactly the pattern in Dijkstra's algorithm and Prim's algorithm on a graph with V vertices and E edges: V extractMin calls but up to E decreaseKey calls. With a binary heap both algorithms cost O((V+E) lg V); with a Fibonacci heap the decreaseKey calls become free (O(1) amortized each), dropping the total to O(E + V lg V) — asymptotically faster whenever E = ω(V) (dense graphs).

The two Dijkstra costs as functions (V = 10⁵ vertices, E = 10⁷ edges gives about 1.7·10⁸ steps with a binary heap and 1.2·10⁷ with a Fibonacci heap, a factor of 14):

In practice, Fibonacci heaps carry large constant factors (extra pointers per node, recursive cutting, cache-unfriendly scattered trees) and are rarely used as-is in production code — most real systems use a d-ary heap or a pairing heap instead, and reach for a genuine Fibonacci heap only when the asymptotic win is provably needed (or to study the theory). Fibonacci heaps are widely described as "mostly of theoretical interest".

Quiz

Interview questions

Cheat sheet

Operation	Actual (worst single call)	Amortized	Space	Notes
`makeHeap`	O(1)	O(1)	O(1)	Empty forest, Φ=0.
INSERT	O(1)	O(1)	O(1)/node	New singleton root; never merges.
MINIMUM	O(1)	O(1)	–	Direct pointer read.
UNION	O(1)	O(1)	–	Splice two root lists; Θ(n) for a binary heap.
`extractMin`	O(n) worst single call	O(lg n)	–	Promotes children, then CONSOLIDATE.
CONSOLIDATE	O(D(n) + t(H))	O(D(n)) = O(lg n)	O(D(n)) array	Merges equal-degree roots via A[0..D].
`decreaseKey`	O(n) worst single call (cascade up a tall tree)	O(1)	–	CUT + possible `cascadingCut` chain.
DELETE	O(n) worst single call	O(lg n)	–	= `decreaseKey`(-∞) + `extractMin`.
Max degree D(n)	D(n) ≤ ⌊logφ n⌋ = O(lg n), φ≈1.618 (golden ratio); ≤ ⌊lg n⌋ without `decreaseKey`/DELETE.

Not in-place (pointer-based forest, not a single array); not stable (no notion of equal-key ordering is preserved). Use a Fibonacci heap when an algorithm performs many decreaseKey calls per extractMin on a dense graph (Dijkstra, Prim); otherwise a binary or d-ary heap is simpler and usually faster in practice.