Fibonacci Heap

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 $O (1)$ amortised cost for insertion and key reduction.

The name “Fibonacci heap” derives from the fact that a node of degree $k$ in a Fibonacci heap has a subtree of size at least $F_{k + 2}$ , where $F_{n}$ is the $n$ -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 $extract-min$ 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 $O (1)$ amortised cost for $decrease-key$ , 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
$find-min$	$O (1)$	$O (1)$
$insert$	$O (1)$	$O (lo g n)$
$union$	$O (1)$	$O (n)$
$extract-min$	$O (lo g n)$	$O (lo g n)$
$decrease-key$	$O (1)$	$O (lo g n)$
$delete$	$O (lo g n)$	$O (lo g n)$

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

Lukas' Notes