HeapsData structureaka lazy mergeable heap

Fibonacci Heap

A collection of heap-ordered trees with lazy consolidation giving amortized O(1) insert, merge, and decrease-key, and O(log n) extract-min.

Pattern: Heap / Priority Queue Practice (2)

Progress

Definition

A Fibonacci heap is a min-priority-queue built from a forest of heap-ordered trees linked in a circular doubly linked root list, plus a pointer to the minimum root. Its claim to fame is amortized O(1) for insert, merge, and decrease-key, with O(log n) amortized extract-min.

The payoff is asymptotic: Dijkstra's Algorithm drops from O((V + E) log V) with a Binary Heap to O(E + V log V), and Prim's Algorithm likewise, because the E decrease-key calls become O(1) each. In practice constant factors and pointer chasing make binary and pairing heaps faster on almost all real inputs.

The structure is lazy: insert just adds a one-node tree to the root list; the actual work — linking trees of equal degree — is deferred until extract-min. The name comes from the bound on tree size: a tree of degree k has at least F(k+2) nodes, where F is the Fibonacci sequence.

amortizedmergeable heapdecrease-keytheoreticalDijkstra bound

Intuition

A mental model before the formal terms.

Imagine a desk where incoming papers are dropped into separate piles instead of being filed. When you need the most urgent paper (the minimum), you finally tidy: you merge piles of the same size, two at a time, so that afterward there is at most one pile per size. Dropping (insert) is free; tidying (extract-min) is paid rarely and cleans up all the accumulated mess at once.

Decrease-key is a quick fix: if a paper becomes more urgent than the pile it sits under, you just rip it out and put it in its own pile at the top. To stop piles from being hollowed out too much, each pile tracks whether it already lost a child ("marked"); losing a second child makes the pile itself get ripped out too (cascading cut).

How it works

Node: key, degree (number of children), mark, and pointers parent, child, left, right (circular sibling list).
Insert(x): create a single-node tree, splice it into the root list, update min if smaller. O(1).
Merge(H1, H2): concatenate the two root lists, keep the smaller min. O(1).
Extract-min: remove min, promote its children to the root list, then consolidate: walk the root list with a degree table A[0..log n]; whenever two roots have the same degree, link the larger under the smaller (degree + 1) and repeat until every degree is unique. Finally rescan roots for the new min. Amortized O(log n).
Decrease-key(x, k): set x.key = k. If x now violates heap order with its parent p, cut x (move it to the root list, clear its mark). If p was already marked, cut p too, and continue upward (cascading cut); otherwise mark p. Amortized O(1).
Delete(x): decrease-key to -∞, then extract-min.

Why it works

Potential function Φ = t + 2m where t is the number of root trees and m the number of marked nodes. Insert raises Φ by 1 (paying for a future link); each link during consolidation lowers t by 1 and pays for itself; each cascading cut lowers m and pays for the next cut.

The mark rule guarantees every node loses at most one child before it is itself cut, so a node of degree k has a subtree of size at least F(k+2) ≥ φ^k. Hence max degree is O(log n), so the degree table and extract-min stay O(log n).

Consolidation is needed only after extract-min; there min had O(log n) children, and the number of trees before consolidation is bounded by prior inserts already paid for by the potential.

Operations

Operation	Description	Cost
insert	Add a single-node tree to the root list.	O(1) amortized
find-min	Return the `min` pointer.	O(1)
merge / union	Splice two root lists together.	O(1) amortized
extract-min	Remove min, promote children, consolidate by degree.	O(log n) amortized
decrease-key	Cut the node to the root list; cascade through marked ancestors.	O(1) amortized
delete	Decrease-key to -∞ then extract-min.	O(log n) amortized

Recognition

How to tell a problem wants this.

A theoretical question: "what is the best known bound for Dijkstra / Prim on dense graphs?" — O(E + V log V) is the Fibonacci-heap bound.
The workload is dominated by decrease-key or merge rather than extract-min.
In interviews it appears almost exclusively as a discussion topic about amortized analysis and priority-queue trade-offs, not as something to implement.

“k most frequent” → Heap / Priority Queue “weighted graph” → Shortest Path (Weighted)

Interactive demo

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1insert(x): add x to root list; if x.key < min.key: min = x
2extract_min():
3  z = min; move each child of z to root list; remove z
4  consolidate(): A = degree table
5    for each root w: while A[w.degree] exists: link larger under smaller; A[old] = null; A[w.degree] = w
6  min = smallest root
7decrease_key(x, k): x.key = k; p = x.parent
8  if p and x.key < p.key: cut(x, p); cascading_cut(p)
9cascading_cut(y): while y.parent: if not y.mark: y.mark = true; return; else cut(y, parent); y = parent

Implementation

1from __future__ import annotations
2 
3 
41 · Node structure and heap state
5class FibNode:
6    __slots__ = ("key", "degree", "mark", "parent", "child", "left", "right")
7 
8    def __init__(self, key: int):
9        self.key = key
10        self.degree = 0
11        self.mark = False
12        self.parent: FibNode | None = None
13        self.child: FibNode | None = None
14        self.left: FibNode = self  # circular doubly linked sibling list
15        self.right: FibNode = self
16 
17 
18class FibonacciHeap:
19    def __init__(self):
20        self._min: FibNode | None = None  # pointer into the root list
21        self._n = 0
22 
23    @staticmethod
24    def _splice_in(at: FibNode, x: FibNode) -> None:
25        x.left = at
26        x.right = at.right
27        at.right.left = x
28        at.right = x
29 
30    @staticmethod
31    def _unlink(x: FibNode) -> None:
32        x.left.right = x.right
33        x.right.left = x.left
34        x.left = x.right = x
35 
362 · Insert and merge (lazy — just extend the root list)
37    def insert(self, key: int) -> FibNode:
38        x = FibNode(key)
39        if self._min is None:
40            self._min = x
41        else:
42            self._splice_in(self._min, x)
43            if x.key < self._min.key:
44                self._min = x
45        self._n += 1
46        return x  # handle needed later for decrease_key
47 
48    def merge(self, other: "FibonacciHeap") -> None:
49        if other._min is None:
50            return
51        if self._min is None:
52            self._min = other._min
53        else:
54            a, b = self._min.right, other._min.right
55            self._min.right, b.left = b, self._min
56            other._min.right, a.left = a, other._min
57            if other._min.key < self._min.key:
58                self._min = other._min
59        self._n += other._n
60        other._min = None
61        other._n = 0
62 
63    def find_min(self) -> int:
64        assert self._min is not None
65        return self._min.key
66 
67    def __len__(self) -> int:
68        return self._n
69 
703 · Extract-min and consolidate
71    def extract_min(self) -> int:
72        z = self._min
73        if z is None:
74            raise IndexError("extract from empty heap")
75        while z.child is not None:  # promote every child to the root list
76            c = z.child
77            z.child = None if c.right is c else c.right
78            self._unlink(c)
79            c.parent = None
80            c.mark = False
81            self._splice_in(z, c)
82        if z.right is z:
83            self._min = None
84        else:
85            self._min = z.right
86            self._unlink(z)
87            self._consolidate()
88        self._n -= 1
89        return z.key
90 
91    def _consolidate(self) -> None:
92        deg: list[FibNode | None] = [None] * 64  # max degree is O(log n)
93        roots = []
94        cur = self._min
95        while True:
96            roots.append(cur)
97            cur = cur.right
98            if cur is self._min:
99                break
100        for x in roots:
101            d = x.degree
102            while deg[d] is not None:  # equal degree: link larger under smaller
103                y = deg[d]
104                if y.key < x.key:
105                    x, y = y, x
106                self._unlink(y)
107                y.parent = x
108                if x.child is None:
109                    x.child = y
110                else:
111                    self._splice_in(x.child, y)
112                x.degree += 1
113                y.mark = False
114                deg[d] = None
115                d += 1
116            deg[d] = x
117        self._min = None  # rebuild the root list from the degree table
118        for r in deg:
119            if r is None:
120                continue
121            r.left = r.right = r
122            if self._min is None:
123                self._min = r
124            else:
125                self._splice_in(self._min, r)
126                if r.key < self._min.key:
127                    self._min = r
128 
1294 · Decrease-key and cascading cut
130    def decrease_key(self, x: FibNode, new_key: int) -> None:
131        if new_key > x.key:
132            raise ValueError("new key is larger than current key")
133        x.key = new_key
134        p = x.parent
135        if p is not None and x.key < p.key:
136            self._cut(x, p)
137            self._cascading_cut(p)
138        if self._min is not None and x.key < self._min.key:
139            self._min = x
140 
141    def _cut(self, x: FibNode, p: FibNode) -> None:
142        if p.child is x:
143            p.child = None if x.right is x else x.right
144        self._unlink(x)
145        p.degree -= 1
146        x.parent = None
147        x.mark = False
148        self._splice_in(self._min, x)
149 
150    def _cascading_cut(self, p: FibNode) -> None:
151        g = p.parent
152        if g is None:
153            return
154        if not p.mark:
155            p.mark = True  # first lost child: mark
156        else:              # second lost child: cut p too
157            self._cut(p, g)
158            self._cascading_cut(g)

Walkthrough

FibNode.__slots__ keeps the seven fields compact; left/right start as self, so a fresh node is a valid circular list.
insert/merge are O(1) root-list splices; merge drains the other heap so no node is owned twice.
extract_min promotes children, unlinks the minimum, and _consolidate links equal-degree trees using a 64-slot degree table before rebuilding the root list.
decrease_key requires the FibNode handle returned by insert; _cut moves a violating node to the roots and _cascading_cut climbs through marked ancestors.
Practical Python note: Dijkstra with heapq plus lazy deletion beats this class on every realistic input — Fibonacci heaps matter for the theory.

Complexity (this implementation)

time O(1) amortized insert/merge/decrease-key, O(log n) amortized extract-min · space O(n)

Per-node Python object overhead dwarfs the binary heap’s flat list; expect large constant factors.

Language notes

Identity checks (is, is not) are correct for the sentinel-free circular lists — nodes are compared by identity, keys by value.
from __future__ import annotations lets FibNode | None annotations evaluate lazily on older 3.x versions.
_cascading_cut is recursive; cut chains are short in practice, but an explicit loop avoids recursion-limit worries on adversarial inputs.

Common mistakes in this language

Using == where is is needed (e.g. cur is self._min to terminate circular-list walks).
Forgetting z.child = None if c.right is c else c.right and looping forever on the last child.
Calling decrease_key with a key larger than the current one — the structure silently breaks without the guard.

Language differences that matter here

All four versions return a node handle from insert — the one API difference from library heaps, and the price of O(1) decrease-key. C++ exposes Node*, the others the node object.
Memory management: C++ needs an explicit recursive destructor and deleted copies; JS/TS/Python let the GC collect the whole forest when the heap is dropped.
Null handling: TS strict null checks force explicit empty-heap branches; Python uses is/is not identity; C++ uses nullptr; JS mixes null (empty) and undefined (return value).
No mainstream standard library ships a Fibonacci heap; C++ has boost::heap::fibonacci_heap, the rest of the ecosystem uses binary/pairing heaps with lazy deletion instead.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Minimum only.
Search	O(n)	O(n)
Insert	O(1)	O(1)	Amortized and actual.
Delete	O(log n)	O(n)	Amortized O(log n); a single call may consolidate O(n) roots.
Update	O(1)	O(n)	Decrease-key amortized O(1); cascading cuts can be long.
Find-min	O(1)	O(1)
Extract-min	O(log n)	O(n)	Amortized O(log n).
Decrease-key	O(1)	O(n)	Amortized O(1).
Merge	O(1)	O(1)
Space	O(n)		Four pointers plus degree and mark per node.

Advantages & disadvantages

Advantages

Best known amortized bounds for a mergeable priority queue with decrease-key.
Improves Dijkstra and Prim to O(E + V log V) on dense graphs.
Merging is O(1) — binary heaps need O(n).

Disadvantages

Large constant factors: four pointers per node, poor cache locality, and complex consolidation. Binary and pairing heaps are faster in practice.
Amortized, not worst-case: a single extract-min can take O(n) after many inserts, which is unacceptable for real-time systems.
Roughly 200 lines of delicate pointer code; almost never written in interviews or production.
Not in standard libraries of Python, Java, C++, JavaScript, or Go.

Use cases

Theoretical analysis of Dijkstra's Algorithm and Prim's Algorithm.
Algorithms whose cost is dominated by decrease-key (some network-flow and matching algorithms).
Teaching amortized analysis with a potential function.

Use it when

Proving asymptotic bounds where decrease-key dominates (dense-graph Dijkstra/Prim).
Priority queues that must be merged in O(1).
Explaining amortized analysis with a potential function.

Avoid it when

Anything performance-sensitive in practice — a Binary Heap (or a pairing heap) is faster on real hardware.
Real-time systems that need worst-case guarantees; use a binary heap or a balanced BST.
Interviews where you are asked to implement a priority queue — write a Binary Heap.
Sparse graphs, where E log V is already close to E + V log V.

Alternatives

Binary Heap Min-Heap Priority Queue Binary Search Tree

Common mistakes

Believing the bounds are worst-case; they are amortized.
Assuming Fibonacci-heap Dijkstra is faster in practice than binary-heap Dijkstra with lazy deletion — it usually is not.
Forgetting to clear the mark when a node is cut to the root list.
Not updating the parent's child pointer when cutting the node it points to.
Consolidating with a degree table too small for log_φ n.

Interview patterns

Compare priority-queue implementations: binary, binomial, Fibonacci, pairing — bounds and trade-offs.
Derive Dijkstra's O(E + V log V) and explain why binary heaps are used anyway.
Explain the potential-function argument for amortized O(1) decrease-key.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Where does O(n log n) come from?Beginner
Top K from a streamIntermediate
When a hash map is the wrong choiceIntermediate

Mock interviews

Kth Largest Element in an ArrayIntermediate
Network Delay TimeAdvanced
Top K Frequent ElementsIntermediate

Interview problems

Network Delay Timemedium Min Cost to Connect All Pointsmedium