Fibonacci Heap Overview

A Fibonacci heap is a heap data structure similar to the binomial heap, only with a few modifications and a looser structure. The Fibonacci heap was designed in order to improve Dijkstra’s shortest path algorithm from O(mlogn) to O(m+nlogn) by optimising the operations used most by the algorithm. Its name derives from the fact that the Fibonacci sequence is used in the complexity analysis of its operations.

The primary difference between the Fibonacci heap and the binomial heap is that it defers all ‘clean up’ jobs to a point where they are more convenient, guaranteeing Θ(1) for several operations. Due to the deferred clean up, the worst case time complexity of the delete and extract minimum operations is O(n), however they are O(logn) amortised.

This article assumes some knowledge of the binomial heap data structure.

Time complexity

* Amortised

Structure

Like the binomial heap, a Fibonacci heap is a collection of heap-ordered trees. They do not need to be binomial trees; however, this is where the relaxation of some of the binomial heap’s properties comes in.

Each tree has an order just like the binomial heap that is based on the number of children. Nodes within a Fibonacci heap can be removed from their tree without restructuring them, so the order does not necessarily indicate the maximum height of the tree or number of nodes it contains.

Some examples of trees of order 0, 1 and 2 (the black nodes are 'marked')

Links

The pointers between nodes in a Fibonacci heap are very similar to that of the binomial heap, only that each node in a Fibonacci heap contains a doubly linked list of all its children. This allows node removal and child list concatenation to both be performed in linear time.

Note that the child node whose parent links to it is always the node with the smallest value among its siblings.

‘Marked’ nodes

An important part of the Fibonacci Heap is how it marks nodes within the trees. The decrease key operation marks a node when its child is cut from a tree; this allows it to track some history about each node. Essentially the marking of nodes allows us to track whether:

• The node has had no children cut (unmarked)
• The node has had a single child cut (marked)
• The node is about to have a second child cut (removing a child of a marked node)

When a second child is cut from its parent, the parent is moved to the root list. This ensures that the structure of the Fibonacci heap does not stray too far from that of the binomial heap, which is one of the properties that enables the data structure to achieve its amortised time bounds.

Operations

Find minimum

A pointer to the minimum node of the root list is always kept up to date.

Insert

Insert creates a new tree containing only the new node which is being added to the heap. The total number of nodes in the tree is incremented and the pointer to the minimum value is updated if necessary.

The insert operation of a Fibonacci heap does not attempt to consolidate trees of equal order, opting instead to defer until a later time.

Union

Union concatenates the root lists of two Fibonacci heaps and sets the minimum node to which ever tree’s minimum node is smaller.

Decrease key

Decrease key lowers the key of a node. The node is then cut from the tree, joining the root list as its own tree. The parent of the node is then cut if it is marked; this continues for each ancestor until a parent that is not marked is encountered, which is then marked. The pointer to the minimum node is then updated if the node’s new value is less than the current minimum.

Extract minimum

Extract minimum is the most complex operation of a Fibonacci Heap as it’s where the actions that were deferred by the other operations occur. It starts by removing the minimum node from the root list and adding its children to the root list.

If the minimum was the only node in the root list, the pointer to the minimum node is set to the smallest node in the root list and the operation is completed.

If not, the ‘consolidate’ operation is performed which merges all trees of the same order together until there are no two trees of the same order. The minimum is then set to the smallest node in the root list.

Delete

Delete is performed by calling decrease key to reduce the node to negative infinity which pulls the node to the top of the tree. Extract minimum is then called on the node to remove it from the heap.

Code

C#

/// <summary>
/// Represents a Fibonacci heap data structure capable of storing generic key-value pairs.
/// </summary>
public class FibonacciHeap<TKey, TValue> : IPriorityQueue<TKey, TValue>
    where TKey : IComparable
{
    // Implementation details...
}

Java

public class FibonacciHeap<T extends Comparable<T>> {
    // Implementation details...
}

JavaScript

'use strict';

var FibonacciHeap = function (customCompare) {
    // Implementation details...
};

TypeScript

export class FibonacciHeap<K, V> {
    // Implementation details...
}

References

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Fibonacci Heaps” in Introduction to Algorithms, 2nd ed., Cambridge, MA: The MIT Press, 2001, ch. 20, pp.476-497

Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) provides a much deeper, math-heavy look.