The following excerpts are from the section *Fibonacci Heap* from the text *Introduction to Algorithms* by *Cormen et. al*

The potential function for the Fibonacci Heaps $H$ is defined as follows:

$$Phi(H)=t(H)+2m(H)$$

where $t(H)$ is the number of trees in the root list of the heap $H$ and $m(H)$ is the number of marked nodes in the heap.

Before diving into the Fibonacci Heap operations the authors try to convince us about the essence of Fibonacci Heaps as follows:

The key idea in the mergeable-heap operations on Fibonacci heaps is to *delay work as long as possible.* **There is a performance trade-off among implementations of the various operations.**($color{green}{text{I do not get why}}$) If the number of trees in a Fibonacci heap is small, then during an $text{Extract-Min}$ operation we can quickly determine which of the remaining nodes becomes the new minimum node( $color{blue}{text{why?}}$ ). However, as we saw with binomial heaps, we pay a price for ensuring that the number of trees is small: it can take up to $Omega (lg n)$ time to insert a node into a binomial heap or to unite two binomial heaps. As we shall see, we do not attempt to consolidate trees in a Fibonacci heap when we insert a new node or unite two heaps. We save the consolidation for the $text{Extract-Min}$ operation, which is when we really need to find the new minimum node.

Now the problem which I am facing with the text is that they dive into proving the amortized cost mathematically using the potential method without going into the vivid intuition of the how or when the “credits” are stored as potential in the heap data structure and when it is actually used up. Moreover in most of the places what is used is “asymptotic” analysis instead of actual mathematical calculations, so it is not quite possible to conjecture whether the constant in $O(1)$ for the amortized cost ( $widehat{c_i}$ ) is greater or less than the constant in $O(1)$ for the actual cost ($c_i$) for an operation.

$$begin{array}{|c|c|c|} hline

text{Sl no.}&text{Operation}&widehat{c_i}&c_i&text{Method of cal. of $widehat{c_i}$}&text{Cal. Steps}&text{Intuition}\ hline

1&text{Make-Fib-Heap}&O(1)&O(1)&text{Asymptotic}&DeltaPhi=0text{ ; $widehat{c_i}=c_i=O(1)$} &text{None}\

hline

2&text{Fib-Heap-Insert}&O(1)&O(1)&text{Asymptotic}&DeltaPhi=1 text{ ; $widehat{c_i}=c_i=O(1)+1=O(1)$} &text{None}\

hline

3&text{Fib-Heap-Min}&O(1)&O(1)&text{Asymptotic}&DeltaPhi=0;text{ ; $widehat{c_i}=c_i=O(1)$} &text{None}\

hline

4&text{Fib-Heap-Union}&O(1)&O(1)&text{Asymptotic}&DeltaPhi=0;text{ ; $widehat{c_i}=c_i=O(1)$} &text{None}\

hline

5&text{Fib-Extract-Min}&O(D(n))&O(D(n)+t(n))&text{Asymptotic}&DeltaPhi=D(n)-t(n)+1 &text{$dagger$}\

hline

6&text{Fib-Heap-Decrease-Key}&O(1)&O(c)&text{Asymptotic}&DeltaPhi=4-c &text{$ddagger$}\

hline

end{array}$$

$dagger$ – The cost of performing each link is paid for by the reduction in potential due to the link’s reducing the number of roots by one.

$ddagger$ – Why the potential function was defined to include a term that is twice the number of marked nodes. When a marked node $у$ is cut by a cascading cut, its mark bit is cleared, so the potential is reduced by $2$. One unit of potential pays for the cut and the clearing of the mark bit, and the other unit compensates for the unit increase in potential due to node $у$ becoming a root.

**Note**: It is quite a difficult question in the sense that it involves the description the problem which I am facing to understand the intuition behind the concept of Fibonacci Heap operations which is in fact related to an entire chapter in the CLRS text. If it demands too much in a single then please do tell me then I shall split it accordingly into parts. I have made my utmost attempt to make the question the clear. If at places the meaning is not clear, then please do tell me then I shall rectify it. The entire corresponding portion of the text can be found here. (Even the authors say that it is a difficult data structure, having only theoretical importance.)