I am trying to get a better understanding of Fibonacci Heaps. I noticed the following definition for the potential function. $$ \Phi(F)=|W| +2\cdot \text{# marks}. $$ I do not understand why it is defined that way, or what its significant is. I am hoping somebody can explain it to me.
1
-
$\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$– Raphael ♦Feb 24, 2018 at 9:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Because it works.
In amortized analysis, you pick the potential function. While it's usually related to some insight about the data structure or algorithm work, is it per se completely arbitrary. The only important thing is that if you write down the telescoping sum -- which is always set up in the same way! -- you can derive a good estimate.
