 Fibonacci heap

A Fibonacci heap implements a meldable priority queue using a collection of 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 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 lists.^[ref]