Amortised Analysis On Fibonacci Heaps

Potential Method For Fibonacci Heap

We define a potential function $\Phi (H)$ for a Fibonacci heap $H$ as:

$$\Phi (H)=\text{nTrees}(H)+2\cdot \text{nMarked}(H)$$

Where:

• $\text{nTrees}(H)$: Number of trees in the root list of $H$
• $\text{nMarked}(H)$: Number of marked nodes in $H$

This potential function captures deferred work:

• Each tree in the root list may need to be consolidated (hence cost).
• Each marked node may trigger a cascading cut (costly), so it’s weighted more heavily (×2).

Example: For a Fibonacci heap with 5 trees and 3 marked nodes:

$$\Phi (H)=5+2(3)=11$$

Amortised Cost Of insert

Let’s analyse the insert() operation using the potential method. Recall the general formula:

$$a_i={\tau }_i+\Phi (H_i)-\Phi (H_{i-1})$$

Where:

• ${\tau }_i$: Actual cost of operation (clearly $O(1)$ for insert). $O(1)$ for insert())
• $\Phi (H_i)$: Potential after the $i$-th insert
• $\Phi (H_{i-1})$: Potential before the $i$-th insert

Inserting an element into $H$ increases the number of trees in the root list by 1 but does not change the number of marked nodes:

1. $\text{nTrees}(H_i)=\text{nTrees}(H_{i-1})+1$
2. $\text{nMarked}(H_i)=\text{nMarked}(H_{i-1})$

So, the change in potential is:

$$\begin{array}{rl}\Phi (H_i)-\Phi (H_{i-1})& =\left[\text{nTrees}(H_i)+2\cdot \text{nMarked}(H_i)\right]-\left[\text{nTrees}(H_{i-1})+2\cdot \text{nMarked}(H_{i-1})\right]\\ & =\left[(\text{nTrees}(H_{i-1})+1)+2\cdot \text{nMarked}(H_{i-1})\right]-\left[\text{nTrees}(H_{i-1})+2\cdot \text{nMarked}(H_{i-1})\right]\\ & =\text{nTrees}(H_{i-1})-\text{nTrees}(H_{i-1})+1+2\cdot \text{nMarked}(H_{i-1})-2\cdot \text{nMarked}(H_{i-1})\\ & =0+1+0\\ & =1\end{array}$$

Hence, the amortised cost per insert operation is:

$$\begin{array}{rl}{a}_i& ={\tau }_i+\Phi (H_i)-\Phi (H_{i-1})\\ & =1+1\\ & =2\end{array}$$

This gives an amortised cost of $O(1)$ for each insert. Additionally, since $\Phi (H_0)=0$, it can be shown that the sum of amortized costs is $O(n)$ and provides an upper bound on the true cost of any sequence of $n$ inserts.

Amortised Cost Of extract-min

For extract-min, the true cost is bounded by:

$${\tau }_i\le {\text{degree}}_{\max }(H_{i-1})+\text{nTrees}(H_{i-1})$$

This is because extracting the minimum root involves:

• Removing that node,
• Promoting its children to the root list, and
• Consolidating the heap to ensure there is at most one tree of any given degree.

Before extraction, the potential is

$$\Phi (H_{i-1})=\text{nTrees}(H_{i-1})+2\cdot \text{nMarked}(H_{i-1})$$

After extraction and consolidation:

• The number of trees is at most $\text{degreemax}(H_i)+1$ because consolidation merges trees of equal degree,
• No new nodes become marked during this operation;
• The extracted node might have been marked, so $\text{nMarked}(H_i)\le \text{nMarked}(H_{i-1})$.

The potential after is thus:

$$\begin{array}{rl}\Phi (H_i)& =\text{nTrees}(H_i)+2\cdot \text{nMarked}(H_i)\\ & \le \text{degreemax}(H_i)+1+2\cdot \text{nMarked}(H_{i-1})\end{array}$$

The change in potential is therefore

$$\begin{array}{rl}\Phi (H_i)-\Phi (H_{i-1})& \le \left(\text{degreemax}(H_i)+1+2\cdot \text{nMarked}(H_{i-1})\right)-\left(\text{nTrees}(H_{i-1})+2\cdot \text{nMarked}(H_{i-1})\right)\\ & =\text{degreemax}(H_i)+1-\text{nTrees}(H_{i-1})\end{array}$$

Substituting into the amortised cost formula results in:

$$\begin{array}{rl}{a}_i& \le \underset{{\tau }_i}{\underbrace{\text{degreemax}(H_{i-1})+\text{nTrees}(H_{i-1})}}+\underset{\Phi (H_i)-\Phi (H_{i-1})}{\underbrace{\text{degreemax}(H_i)+1-\text{nTrees}(H_{i-1})}}\\ a_i& =\text{degreemax}(H_i)+\text{degreemax}(H_{i-1})+1.\end{array}$$

Since the maximum degree ${\text{degree}}_{\max }(H)$ grows asymptotically as $O(\log |H|)$, where $|H|$ is the number of elements in the heap, the amortised cost of extract-min is therefore

$$a_i=O(\log |H|).$$

Amortised Cost Of decrease-key

For decrease-key, suppose the operation on the heap state $H_{i-1}$ results in $m\ge 0$ nodes being promoted to the root level through cascading cuts. The true cost is

$${\tau }_i=O(m),$$

because each cascading cut to promote a node to the root takes constant time $O(1)$.

Before the operation, the potential is

$$\Phi (H_{i-1})=\text{nTrees}(H_{i-1})+2\cdot \text{nMarked}(H_{i-1}).$$

After decreasing the key and promoting $m$ nodes, the potential satisfies

$$\begin{array}{rl}\Phi (H_i)& =\text{nTrees}(H_i)+2\cdot \text{nMarked}(H_i)\\ & \le \text{nTrees}(H_{i-1})+m+2\left(\text{nMarked}(H_{i-1})-(m-1)+1\right).\end{array}$$

This inequality holds because:

• At least $m-1$ and at most $m$ previously marked nodes are promoted to the root and thus become unmarked, reducing the marked count,
• The final cascading cut might mark its previously unmarked parent, increasing the marked count by 1.

Therefore, the change in potential is

$$\begin{array}{rl}\Phi (H_i)-\Phi (H_{i-1})& \le \left(\text{nTrees}(H_{i-1})+m+2\cdot \text{nMarked}(H_{i-1})-2(m-1)+2\right)\\ & -\left(\text{nTrees}(H_{i-1})+2\cdot \text{nMarked}(H_{i-1})\right)\\ & =m-2m+2+2\\ & =-m+4.\end{array}$$

Substituting into the amortised cost formula yields

$$\begin{array}{rl}{a}_i& ={\tau }_i+\Phi (H_i)-\Phi (H_{i-1})\\ & \le m+(-m+4)\\ & =4.\end{array}$$

Thus, the amortised cost of decrease-key is $O(1)$.

Intuition Behind The Chosen Potential

To understand the intuition behind the chosen potential function for Fibonacci heaps, recall that all operations can affect:

• the number of trees in the root list, and
• the number of marked nodes in the heap (particularly during decrease-key).

It is therefore natural to define a potential function based on these two quantities. The standard potential used is:

$$\Phi (H)=\text{nTrees}(H)+2\cdot \text{nMarked}(H)$$

However, this still leaves the question: why exactly the constants 1 and 2?

To explore this, assume a generalised potential function:

$$\Phi (H)={\lambda }_1\cdot \text{nTrees}(H)+{\lambda }_2\cdot \text{nMarked}(H)$$

Let’s revisit the amortised analysis of decrease-key using this form.

Before the operation:

$$\Phi (H_{i-1})={\lambda }_1\cdot \text{nTrees}(H_{i-1})+{\lambda }_2\cdot \text{nMarked}(H_{i-1})$$

After decreasing the key and promoting $m$ nodes:

• The number of trees increases by $m$,
• The number of marked nodes decreases by at least $m-1$, but can increase by 1 due to the final cascading cut.

So the potential becomes:

$$\Phi (H_i)\le {\lambda }_1(\text{nTrees}(H_{i-1})+m)+{\lambda }_2(\text{nMarked}(H_{i-1})-(m-1)+1)$$

Now compute the amortised cost:

$$\begin{array}{rl}{a}_i& ={\tau }_i+\Phi (H_i)-\Phi (H_{i-1})\\ & \le m+{\lambda }_1(\text{nTrees}(H_{i-1})+m)+{\lambda }_2(\text{nMarked}(H_{i-1})-(m-1)+1)\\ & -{\lambda }_1\cdot \text{nTrees}(H_{i-1})-{\lambda }_2\cdot \text{nMarked}(H_{i-1})\\ & =m+{\lambda }_{1}m+{\lambda }_2(-m+2)\\ & =(1+{\lambda }_1-{\lambda }_2)m+2{\lambda }_2\end{array}$$

This result is not useful as an amortised bound, because the right-hand side still depends on $m$, which varies per operation.

To eliminate this dependency, we want the coefficient of $m$ to vanish:

$$1+{\lambda }_1-{\lambda }_2=0$$

Solving this gives the natural choice:

$${\lambda }_1=1,{\lambda }_2=2$$

So, defining the potential as

$$\Phi (H)=\text{nTrees}(H)+2\cdot \text{nMarked}(H)$$

makes the amortised cost of decrease-key independent of $m$, yielding a clean $O(1)$ bound.