Fibonacci heaps

Basic idea

A heap of rooted trees with lazy consolidation. Achieves $O(1)$ amortised for insert and decrease-key, making Dijkstra and Prim run in $O(E + V\log V)$. Heavy hidden constants make it more theoretical than practical.

Key formulas

• insert, find-min, merge, decrease-key: $O(1)$ amortised
• delete-min, delete: $O(\log n)$ amortised
• Max degree of any node: $D(n) \le \log_\phi n$

Siblings

• Adaptive Radix Tree
• Bloom filter
• Cache Oblivious Algorithms & Datastructures
• Count-min sketch
• CTrie
• Disjoint Set
• Fenwick tree
• Finger-Trees
• GeoHash
• Hash Array Mapped Tries
• Hash Tables
• Hilbert-R Tree
• HyperLogLog
• Judy Arrays
• k-d Tree
• Links
• M Tree
• Pairing heaps
• R tree
• RRB-Trees
• Segment Trees
• Sparse Sets
• Succint Datastructures