1
$\begingroup$

Suppose that you do some sequence of operations on a max heap, in this case only Insert and 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 2N.

The goal is to come up with a potential function to analyze the amortized cost of Insert and 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).

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You try to imitate examples you know, and after some trial and failure you eventually succeed (hopefully). $\endgroup$
    – Yuval Filmus
    Commented Mar 27, 2015 at 0:29
  • $\begingroup$ This is for the standard binary heap? IIRC, both operations have $\Theta(\log n)$ worst-case runtime, both amortized and not. $\endgroup$
    – Raphael
    Commented Mar 27, 2015 at 6:13
  • $\begingroup$ @Yuval, isn't there something that can indicate which functions might give more tight bounds than other functions? Raphael, yes you are right. It's just that for this exercise we want to find the kind of potential function that will give us the running times specified in the problem statmeent. $\endgroup$
    – jsguy
    Commented Mar 27, 2015 at 15:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.