12
$\begingroup$

I need help figuring the potential function for a max heap so that extract max is completed in $O(1)$ amortised time. I should add that I do not have a good understanding of the potential method.

I know that the insert function should "pay" more in order to reduce the cost of the extraction, and this has to be in regards to the height of the heap (if $ \lfloor \log(n) \rfloor $ gives the height of the heap should the insert be $2\log(n)$ or $ \sum_{k=1}^n 2\log(k) $)

$\endgroup$

1 Answer 1

14
$\begingroup$

Try the following:

The weight $w_i$ of an element $i$ in the heap $H$ is its depth in the corresponding binary tree. So the element in the root has weight zero, its two children have weight 1 and so on. The you define as potential function

$$\Phi(H)=\sum_{i\in H}2 w_i.$$

Let us now analyze the heap operations. For insert you add a new element add depth $d$ at most $\log(n)$. This increases the potential by $2d$, and can be done in $O(1)$ time. Then you "bubble up" the new heap element to assure the heap-property. This takes $O(\log n)$ time and leaves $\Phi(H)$ unchanged. Thus the costs for insert are $O(\log(n)+\Delta(\Phi(H)))=O(\log n)$.

Now consider the extractMin. You take out the root and replace it by the last element in the heap. This decreases the potential by $2\log(n)$, thus you can afford to repair the heap property, and therefore the amortized costs are now $O(1)$.

If you have a general question for the potential function you should pose this as a different question.

$\endgroup$
5
  • $\begingroup$ I'm sure you are correct but I did not understand the insertion. Why is $\Delta(\Phi(H)))$ unchanged ? Sorry if the answer is obvious but could you please expand $\Delta$ ? I can't see why you would have a negative number there $\endgroup$
    – andrei
    Jan 12, 2013 at 12:19
  • $\begingroup$ $\Delta(\Phi(H))$ refers to the potential difference - before and after the insert. It is in the insert case at most $2\log(n)$. When you exchange two elements in the heap (bubble-up or bubble-down), then one weight gets +1, and the other gets -1 change, thus the potential (the sum of all weights) remains the same. $\endgroup$
    – A.Schulz
    Jan 12, 2013 at 13:39
  • $\begingroup$ How is repair O(1)? What is the use of the potential function in repairing the heap? Could you please clarify $\endgroup$
    – Sohaib
    Jan 28, 2015 at 18:16
  • $\begingroup$ @Sohaib: repair takes $O(\log n)$ time, but $O(1)$ amortized time using the above potential function. There is no other use of the potential function than analyzing the amortized costs. $\endgroup$
    – A.Schulz
    Jan 28, 2015 at 21:19
  • $\begingroup$ @A.Schulz So this in essence means that given that the extract operation is done n number of times since each time the potential function would decrease by 2logn (may or may not increase equally upon repair). The overall complexity for such a thing would be constant time since eventually there would be no node in the tree. Am I right? $\endgroup$
    – Sohaib
    Jan 29, 2015 at 16:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.