In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis.

The amortized times of all operations on Fibonacci heaps is constant, except delete-min.

  1. They are complicated to implement.
  2. They are not as efficient in practice when compared with theoretically less efficient forms of heaps. In their simplest version, they require manipulation of four pointers per node, whereas only two or three pointers per node are needed in other structures, such as the binomial heap, or pairing heap. This results in large memory consumption per node and high constant factors on all operations.

Although the total running time of a sequence of operations starting with an empty structure is bounded by the bounds given above, some (very few) operations in the sequence can take very long to complete (in particular, delete-min has linear running time in the worst case). For this reason, Fibonacci heaps and other amortized data structures may not be appropriate for real-time systems.

It is possible to create a data structure which has the same worst-case performance as the Fibonacci heap has amortized performance. One such structure, the Brodal queue, is, in the words of the creator, "quite complicated" and "[not] applicable in practice." Invented in 2012, the strict Fibonacci heap is a simpler (compared to Brodal's) structure with the same worst-case bounds. Despite being simpler, experiments show that in practice the strict Fibonacci heap performs slower than more complicated Brodal queue and also slower than basic Fibonacci heap. The run-relaxed heaps of Driscoll et al. give good worst-case performance for all Fibonacci heap operations except merge. Recent experimental results suggest that the Fibonacci heap is more efficient in practice than most of its later derivatives, including quake heaps, violation heaps, strict Fibonacci heaps, and rank pairing heaps, but less efficient than pairing heaps or array-based heaps.