AlgoScope

Fibonacci Heap

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

Data structures, data structure, expert
7 extracted. Consolidating.heap234115301952

Binomial and Fibonacci Heaps: Fibonacci extract-min pays for the lazy inserts

Decision, step 2 of 7

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.

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.

Leads to

Topics that need this one first.

Taught by the same lesson

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