Fibonacci heap

In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees.

Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987.

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

In a binary or binomial heap, such a sequence of operations would take

Using Fibonacci heaps improves the asymptotic running time of algorithms which utilize priority queues.

A Fibonacci heap is a collection of trees satisfying the minimum-heap property, that is, the key of a child is always greater than or equal to the key of the parent.

For example, merging heaps is done simply by concatenating the two lists of trees, and operation decrease key sometimes cuts a node from its parent and forms a new tree.

However, at some point order needs to be introduced to the heap to achieve the desired running time.

This is achieved by the rule: at most one child can be cut off each non-root node.

As a result of a relaxed structure, some operations can take a long time while others are done very quickly.

For the amortized running time analysis, we use the potential method, in that we pretend that very fast operations take a little bit longer than they actually do.

The amount of time saved for later use is measured at any given moment by a potential function.

Thus, the root of each tree in a heap has one unit of time stored.

We maintain a pointer to the root containing the minimum key, allowing

This pointer must be updated during the other operations, which adds only a constant time overhead.

The node is simply appended to the root list, increasing the potential by one.

The delete-min operation does most of the work in restoring the structure of the heap.

We then initiate a series of cascading cuts, starting with the parent of

As long as the current node is marked, it is cut from its parent and made an unmarked root.

The amortized performance of a Fibonacci heap depends on the degree (number of children) of any tree root being

The degree bound follows from this and the fact (easily proved by induction) that

be an arbitrary node in a Fibonacci heap, not necessarily a root.

, indexed in order of the times they were most recently made children of

Since trees are combined only when the degrees of their roots are equal, it must have been the case that

could have only lost at most one child (as guaranteed by the marking process), and so its current degree

Although Fibonacci heaps look very efficient, they have the following two drawbacks:[3] 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.

One such structure, the Brodal queue,[5] is, in the words of the creator, "quite complicated" and "[not] applicable in practice."

Invented in 2012, the strict Fibonacci heap[6] 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.

Figure 1. Example of a Fibonacci heap. It has three trees of degrees 0, 1 and 3. Three vertices are marked (shown in blue). Therefore, the potential of the heap is 9 (3 trees + 2 × (3 marked-vertices)).
Figure 2. First phase of delete-min .
Figure 3. Third phase of delete-min .
Figure 4. Fibonacci heap from Figure 1 after decreasing key of node 9 to 0.