Fibonacci Heaps: The Potential Function

The Potential Method (Review)

For any data structure, define a potential function $\Phi(D) \ge 0$ that maps each state $D$ of the structure to a non-negative real number, with $\Phi(D_0) = 0$ for the initial (empty) state. The amortised cost of an operation is:

$\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$

where $c_i$ is the actual cost and $\Phi(D_i) - \Phi(D_{i-1})$ is the change in potential. Over $m$ operations,

$\sum_{i=1}^{m} \hat{c}_i = \sum_{i=1}^{m} c_i + \Phi(D_m) - \Phi(D_0) \ge \sum_{i=1}^{m} c_i$

so amortised costs upper-bound actual costs.

Fibonacci Heap Potential

The potential function for a Fibonacci heap is:

$\Phi = r + 2m$

where:

• $r$ = number of trees in the root list (number of roots)
• $m$ = number of marked nodes (nodes with marked = true)

Check: For an empty heap, Create returns (NIL, 0), so $r = 0$, $m = 0$, and $\Phi = 0$ (valid initial state, non-negative).

Amortised Analysis of Each Operation

Insert

Actual cost: $\Theta(1)$. The new node is added to the root list as a singleton. It is never marked. $r$ increases by 1; $m$ unchanged.

$\Delta \Phi = (r+1 + 2m) - (r + 2m) = 1$

$\hat{c} = \Theta(1) + 1 = \Theta(1)$

Destructive Union

Actual cost: $\Theta(1)$. Root lists are spliced together; no marks change. Combined potential:

$\Phi' = (r_1 + r_2) + 2(m_1 + m_2) = \Phi_1 + \Phi_2$

$\Delta \Phi = \Phi' - (\Phi_1 + \Phi_2) = 0$

$\hat{c} = \Theta(1) + 0 = \Theta(1)$

Decrease-Key

Three cases depending on whether cutting occurs:

Case 1 — No cut (new key $\ge$ parent’s key): No structural change. $\Delta\Phi = 0$, $\hat{c} = \Theta(1)$.

Case 2 — Single cut, parent was unmarked: Node x goes to root list ($r$ +1). x becomes unmarked (if it was marked, $m$ -1; if not, $m$ unchanged). Parent p becomes marked ($m$ +1).

• If x was unmarked: $\Delta\Phi = (r+1 + 2(m+1)) - (r + 2m) = 3$
• If x was marked: $\Delta\Phi = (r+1 + 2(m)) - (r + 2m) = 1$

In both cases, $\Delta\Phi \in \Theta(1)$, so $\hat{c} = \Theta(1)$.

Case 3 — Cascading cut: $a$ nodes are cut and moved to root list. Each cut node was marked (so $m$ decreases by $a$). Each enters the root list ($r$ increases by $a$). The node whose key was decreased also enters the root list ($r$ +1). The final stop may mark one parent ($m$ +1, or 0 if parent is a root).

$\Delta\Phi = (r+1+a) + 2(m-a) - (r+2m) = 1 + a - 2a = 1 - a$

Actual cost is $k_1 + a \cdot k_2$. Setting $k_2 = 1$ (each cut takes constant time):

$\hat{c} = (k_1 + a) + (1 - a) = k_1 + 1 = \Theta(1)$

The cascading work is “paid for” by the decrease in $m$: each cut node was marked, contributing 2 to the potential; when it is unmarked on entering the root list, those 2 units are released to pay for the cut.

Extract-Min

Actual cost: $O(r + D(n))$ where $D(n)$ is the maximum degree and $r$ is pre-operation root list size.

• Promote children of min (at most $D(n)$ children): each child joins root list, $r$ increases by up to $D(n)$.
• One root removed.
• Consolidation scans $r + D(n) - 1$ roots, merging trees of equal degree.
• After consolidation: at most $D(n)+1$ trees remain.

Potential before: $\Phi_1 = r + 2m$. Potential after (worst case): $\Phi_2 = (D(n)+1) + 2m$. Change: $\Delta\Phi = D(n)+1 - r$.

$\hat{c} = O(r + D(n)) + (D(n) + 1 - r) = O(D(n))$

Since $D(n) = O(\log n)$ (proved by the degree bound), $\hat{c} = O(\log n)$. The large $r$ term in actual cost is cancelled by the corresponding decrease in potential (the “credit” that insert and decrease-key built up).

Intuition Behind the Potential

The term $r$ pays for scanning the root list during extract-min. Each insert adds 1 to $r$ and 1 to potential. The term $2m$ pays for cascading cuts: when a node is marked, 2 units are deposited; one unit pays for the cut itself, the other for the node now occupying space in the root list (adding to the cost of future extract-min).

Summary

Operation	$\Delta\Phi$	Amortised Cost
Insert	$+1$	$\Theta(1)$
Destructive-union	$0$	$\Theta(1)$
Decrease-key (no cut)	$0$	$\Theta(1)$
Decrease-key (single cut)	$1$ or $3$	$\Theta(1)$
Decrease-key (cascading)	$1-a$	$\Theta(1)$
Extract-min	$D(n)+1-r$	$\Theta(\log n)$

Key insight: The potential $\Phi = r + 2m$ captures the “repair work” deferred by lazy insert and decrease-key operations, releasing credit exactly when extract-min needs to perform consolidation.