Fibonacci Heap

data-structures algorithms graph-theory

Definition

Fibonacci Heap

A Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It provides better amortised time complexity than binary or binomial heaps for several operations, specifically supporting amortised cost for insertion and key reduction.

The name “Fibonacci heap” derives from the fact that a node of degree in a Fibonacci heap has a subtree of size at least , where is the -th Fibonacci number (though the golden ratio is more directly involved in the bounds).

Structure and Implementation

A Fibonacci heap is a forest of heap-ordered trees. Unlike binomial heaps, the trees in a Fibonacci heap do not have a prescribed shape. The roots of these trees are stored in a circular, doubly linked list, referred to as the root list.

Operations

Consolidation

During an operation, the heap performs a consolidation step. This process reduces the number of trees in the root list by linking roots of equal degree until every root has a unique degree. This ensures the number of trees remains logarithmic relative to the number of nodes.

Decrease Key and Marking

To maintain the amortised cost for , Fibonacci heaps use a “marking” system. When a child is cut from its parent (due to its key becoming smaller than its parent’s), the parent is marked. If a marked node loses another child, it is also cut and moved to the root list, potentially causing a cascading cut.

Complexity

The following table lists the amortised time complexity for a Fibonacci heap compared to a standard binary heap:

Operation	Fibonacci Heap	Binary Heap

Fibonacci heaps are particularly efficient for algorithms like Dijkstra’s algorithm where operations are frequent.