Fibonacci Heap

Data structureexpertHeaps

A lazy mergeable heap with O(1) amortized decrease-key, the theoretical best for Dijkstra.

Decision · step 2 of 7Binomial and Fibonacci Heaps: Fibonacci extract-min pays for the lazy inserts

7 is removed. 6 roots remain, all of degree 0, so consolidation will link them in pairs and the pairs in pairs: at least 5 links before every degree is unique.

Open in the player →or start at step 2

What you will see

Roots in a circular list; consolidation links trees of equal degree.

How binomial and fibonacci heaps works →

Cost

insert	`O(1) amortized`
decrease key	`O(1) amortized`
extract min	`O(log n) amortized`
Space	`O(n)`

Rarely used in practice; large constants.

How you work with it here

play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.

Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.

Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.

Before this

Binomial Heap Potential Method

Dijkstra

Leads to

Topics that need this one first.

Fibonacci Heap Decrease-Key

Taught by the same lesson

Binomial and Fibonacci Heaps covers these too, in the same run.

Binomial Heap Binomial Heap Merge Fibonacci Heap Decrease-Key