DSAverse

Heap-like Data Structures

Loading Heap Structures...

Max Heap

root: 90

Fibonacci Heap

A lazy heap that defers all restructuring to extract-min. Insert and decrease-key run in O(1) amortized — critical for fast graph algorithms.

Speed

Empty heap — insert values to begin

Root Trees

—

Min Key

Total Nodes

Minimum node Active step Regular node

Insert several values, then try Extract Min to see consolidation in action.

O(1)

Insert

O(1)

Peek Min

O(log n)*

Extract Min

O(1)*

Decrease Key

O(1)

Merge

O(n)

Space

* amortized — O(log n) worst case for extract-min

•Lazy insert — new nodes go straight to root list, O(1)
•Deferred consolidation — linking only happens during extract-min
•Degree bound — after consolidation, max degree is O(log n)
•Min pointer — always tracks the root with the smallest key
•Marked nodes — track which non-root nodes have lost a child (for decrease-key cascading cuts)

•Dijkstra's — O(E + V log V) with Fibonacci heap vs O((E+V) log V) with binary heap
•Prim's MST — same improvement for dense graphs
•Primarily theoretical value — large constants make binary heaps faster in practice for typical n

Question 1 of 3

What is the amortized time complexity of inserting into a Fibonacci heap?

Heap-like Data Structures

Loading Heap Structures...

Max Heap

root: 90