Fibonacci Heaps: Motivation and Structure

Motivation

Dijkstra’s algorithm with a binary heap runs in $\Theta((V+E)\log V)$. With a Fibonacci heap, the running time drops to $\Theta(V \log V + E)$, which is better when $E$ is super-linear in $V$ (i.e. for dense graphs). The critical improvement: decrease-key costs $\Theta(\log n)$ in a binary heap but only $\Theta(1)$ amortised in a Fibonacci heap.

Dijkstra calls insert $O(V)$ times, extract-min $O(V)$ times, and decrease-key $O(E)$ times. The per-operation costs determine overall complexity:

Operation	Binary Heap	Fibonacci Heap
insert	$O(\log V)$	$O(1)$ amortised
extract-min	$O(\log V)$	$O(\log V)$ amortised
decrease-key	$O(\log V)$	$O(1)$ amortised
Dijkstra total	$O((V+E)\log V)$	$O(V \log V + E)$

FibHeaps also support destructive-union (merge two heaps) in $O(1)$ amortised time, versus $\Theta(n_1+n_2)$ for binary heaps.

Structure Overview

A Fibonacci heap is a collection of min-heap-ordered trees. This is similar to a binomial heap but the structure is maintained more lazily: rather than enforcing the binomial shape at every step, violations are allowed to accumulate and are cleaned up only during extract-min.

Root List

The trees are held in a circular, doubly linked list called the root list. There is no ordering amongst the roots; any root can be the minimum. A min pointer always tracks the current minimum root, maintained at $\Theta(1)$.

Node Attributes

Each node stores eight fields:

1. key — the priority value (duplicates permitted)
2. payload — the data associated with the key
3. left — pointer to left sibling
4. right — pointer to right sibling
5. parent — pointer to parent (NIL for root nodes)
6. child — pointer to any one child (NIL if no children)
7. degree — number of immediate children
8. marked — boolean: has this node lost a child since it became a child of its current parent?

Children are held in unordered, circular, doubly linked lists (same as the root list). A pointer to a child node gives access to its entire sibling list; the exact position within the list does not matter because the lists are unordered.

The Fibonacci Heap Handle

A Fibonacci heap reference is a 2-tuple (min_ptr, n) where min_ptr points to the node containing the current minimum key and n is the total number of keys present.

Key Structural Rules

• Nodes in the root list are never marked.
• If a node’s key is decreased below its parent’s key (violating heap order), it is cut from its parent and moved to the root list. Its parent becomes marked (or, if already marked, is itself cut — the cascading cut).
• Consolidation (merging trees of equal degree) is performed only during extract-min, bringing the root list back to at most $O(\log n)$ trees.

Worked Example: State After Insertions

Suppose we insert keys 5, 3, 7, 2, 4, 1, 6 in that order into an empty FibHeap. After all inserts (each just adds a singleton to the root list), the root list contains all seven nodes as singletons (all degree 0). The min pointer points to 1. No consolidation has occurred yet; that happens only on extract-min.

Root list: [1] <-> [6] <-> [4] <-> [2] <-> [7] <-> [3] <-> [5]
min_ptr -> 1
n = 7

Summary

Property	Detail
Structure	Collection of min-heap-ordered trees
Root list	Circular doubly linked, unordered
Child lists	Circular doubly linked, unordered per node
Node fields	key, payload, left, right, parent, child, degree, marked
Min pointer	Direct pointer to minimum root, $\Theta(1)$
Mark bit	Tracks whether node has lost a child since becoming a child
Key advantage	decrease-key in $\Theta(1)$ amortised
Lazy strategy	Work deferred to extract-min (consolidation)