# Potential function binary heap extract max O(1)

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

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.

• 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
• How is repair O(1)? What is the use of the potential function in repairing the heap? Could you please clarify – Sohaib Jan 28 '15 at 18:16
• @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. – A.Schulz Jan 28 '15 at 21:19
• @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? – Sohaib Jan 29 '15 at 16:24