# give potential function - binary heap - extract-min in amortized const time and insert in log amortized time

Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in O($\lg n)$ worst-case time. Give a potential function $\Phi$ such that the amortized cost of INSERT is $O(\lg n)$ and the amortized cost of EXTRACT-MIN is $O(1)$.

I try to solve it, but I got in stuck:

Attempt
Let $c_i$ denotes real cost of $i-th$ operation, and $a_i$ denotes amortized cost.
Let $\Phi(D_i) = \text{number of elements after i operations}$
INSERT:$$a_i=c_i+ \Phi(D_i) - \Phi(D_{i-1}) \le \log(i) + (i)\log(i) - (i-1)\log(i-1) \le 3\log(i+1) = O(\log(i))$$
EXCTRACT-MIN:$$a_i=c_i + \Phi(D_i) - \Phi(D_{i-1}) \le \log(i) + i\log(i) - (i+1)\log(i+1) =\log(i) + i\log(i) - i\log(i+1) - \log(i+1) < 0$$

As you can see, my problem is that I get number lower than $0$. Can you help me ?

• Where are you getting that that $\Phi(D_i) = i\log(i)$, if it's the number of elements? How can I have $i\log(i)$ elements after $i$ operations? – Alex Meiburg Sep 3 '15 at 12:21
• Ok, It was not OK. My potential function is number of nodes. – M.Swe Sep 3 '15 at 12:23
• OK. In that case, please edit your question to adjust it and fix the error. Don't just leave clarifications in the comments: edit your question to correct any mistakes/ambiguities/etc. Questions should be self-contained -- people shouldn't have to read the comments to understand your question -- and comments can disappear at any time. – D.W. Sep 3 '15 at 17:03

Let's review the potential function method. Suppose that the $i$th operation costs $c_i$ and the value of the potential function at time $i$ is $\Phi_i \geq 0$, and that $\Phi_0 = 0$ (the potential at the beginning). Define the amortized operation costs by $a_i = c_i + \Phi_i - \Phi_{i-1}$. Then $$\sum_{i=1}^n a_i = \sum_{i=1}^n (c_i + \Phi_i - \Phi_{i-1}) = \sum_{i=1}^n c_i + \Phi_n - \Phi_0 \geq \sum_{i=1}^n c_i.$$ This means that the total amortized cost $\sum_{i=1}^n a_i$ is an upper bound on the actual cost $\sum_{i=1}^n c_i$, which is what we want.
Back to your case. Suppose that inserting the $n$ element costs $\log n$, and extracting the minimum when there are $n$ elements also costs $\log n$. This suggests a charging argument in which we charge the insertion of the $n$th element by $2\log n$, and discharge the extra $\log n$ when extracting the minimum the next time that there are exactly $n$ elements. This gives an amortized time of $O(\log n)$ for insertion, and $0$ for extract-min.
We can give a similar argument using a potential function. We choose a potential function of the form $\sum_{i=1}^n \log i$, where $n$ is the current number of elements. Under this potential function, insertion costs $2\log n$ and extract-min costs $0$.
Note that $\sum_{i=1}^n \log i = \log n! \approx n\log n$, so this differs from your suggestion (appearing in the comments) of using $n$ as a potential function; your suggestion doesn't work, since under it extract-min costs $$\log n + n - (n-1) = \log n - 1.$$ Taking a closer look at your question, you are actually using the potential function $n\log n$, which is very similar to what I suggest. This potential function does work.