Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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) $)

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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 –  andrei Jan 12 '13 at 12:19
    
$\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. –  A.Schulz Jan 12 '13 at 13:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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