Suppose that you do some sequence of operations on a max heap, in this case only
Extract-max. Whenever the heap becomes of size
N then what you do is you copy all the elements to a new heap of size
The goal is to come up with a potential function to analyze the amortized cost of
Extract-max. More specifically for insert it should be $O(\log n)$ and for extract-max it should be $O(1)$
I understand the idea behind the potential method, that you store the potential energy for each object in your data structure that might be released in the future. But how exactly do you come up with these functions? The answer to the above problem is $\Phi = |2n-N|+\log n$ but I am not sure how to come up with it.
I tried searching online for some examples but I couldn't really find anything significant, every example was some kind of over simplified generalization of some trivial problem(here for instance).