Fibonacci Heaps

Standard heap structures like binary heaps are inefficient for merge and decrease-key operations, taking linear and logarithmic time respectively.

This reduces performance in algorithms with frequent priority updates or heap merges like Dijkstra’s Algorithm, whose time complexity depends on the cost of extract-min and decrease-key:

$O(|V|\times {\text{Time}}_{\text{extract-min}}+|E|\times {\text{Time}}_{\text{decrease-key}})$

Using a binary heap, this becomes:

$O(|V|\log |V|+|E|\log |V|)\approx O(|E|\log |V|)$

In contrast, Fibonacci Heaps reduce the amortised cost of decrease-key to $O(1)$, while keeping extract-min at $O(\log |V|)$:

$O(|V|\log |V|+|E|)\approx O(|E|)$

These notes assume a min-heap however all operations can be adapted to a max-heap.

Fibonacci Heaps

A Fibonacci Heap is a collection of heap-ordered trees where the roots are linked in a Circular Doubly Linked List, and each node’s children are connected in their own circular doubly linked list.

Each node stores:

• A key with an associated payload,
• Its degree (number of children)
• A marked flag (used in decrease-key), and
• Pointers to its parent, any one child, and its left and right siblings.

The heap is accessed via a pointer min referencing the root with the minimum key.

Node Structure Illustrations

Example Of Fibonacci Heaps

Below is a Fibonacci heap with $5$ trees and $14$ elements. Each tree maintains the min-heap property, and the H.min pointer references node 3, the smallest in the heap.

Design Of Fibonacci Heaps

An important invariant of Fibonacci heaps is that no two trees in the root list can have the same degree, however, it is only enforced during extract-min via the consolidate step.

This lazy restructuring and utilisation of circular doubly linked lists achieves:

• Amortised constant time for insert and decrease-key operations
• Amortised logarithmic time for extract-min and delete
• Constant time for merge

Though more complex and with higher overhead, Fibonacci heaps support a broader set of heap operations more efficiently than binary or binomial heaps, making them valuable for algorithms with frequent priority updates, like Dijkstra’s or Prim’s.