= Fibonacci heap
{c}
A <Fibonacci heap> implements a meldable <priority queue> using a collection of <heap order>[heap-ordered trees] and a pointer to a minimum. Insertion and melding defer consolidation. Removing the minimum promotes its children and repeatedly links roots with equal numbers of children, keeping the smaller key above the larger. Decreasing a key cuts a violating node; mark bits and cascading cuts control how much child loss a retained node may accumulate.
The <potential method> charges stored work using the number of <tree (graph theory)>[tree] roots plus twice the number of marked nodes. It yields constant <amortized cost> for insertion, melding and decrease-key, and $O(\log n)$ for removing the minimum. These are sequence guarantees, not worst-case bounds for each operation. A node with $k$ children has at least a Fibonacci-sized <subtree>, bounding $k$ logarithmically in total heap size. The inexpensive decrease-key operation improves <Dijkstra's algorithm> to $O(m+n\log n)$ with <adjacency list>[adjacency lists].<Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms by Michael L. Fredman and Robert Endre Tarjan>[§§2–3, operations and analysis]{ref}
Back to article page
