3
$\begingroup$

I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function.

We can assume, that insert is O(logn) and delete-min is O(logn) too.

The goal is to prove, that amortised price of insert is O(logn) and amortised price of delete-min is O(1).

Can't figure out how to create a potential function.

POT.F = ?
INSERT c = logn + (something from 0 to xlogn)
DELETE-MIN c = logn + (something like -logn) 

Could you guys help me? I've figure out so far that difference between potentials should be from 0 to xlogn so INSERT price would be logn and for DELETE-MIN, difference should be somewhere abour -logn to get constant price.

$\endgroup$
  • $\begingroup$ What kind of sequence of operations do you want to amortize over? $\endgroup$ – Raphael Jun 22 '16 at 16:49
  • $\begingroup$ @raphael - any possible sequence of these two operations. So you can't delete-min if you did not push before etc. $\endgroup$ – Milano Jun 22 '16 at 16:58
  • $\begingroup$ I don't think that's possible. How to amortize for sequences with only one delete-min? Do you want to average over all sequences? $\endgroup$ – Raphael Jun 22 '16 at 17:00
  • $\begingroup$ For example for operations PUSH and POP, we can say that their amortised price is PUSH = 2 POP = 0. If Pot. Function is size of stack, then PUSH = 1 + S+1 - S = 2 and POP = 1 + S-1 - S = 0. I mean it in this way. $\endgroup$ – Milano Jun 22 '16 at 19:01
  • 1
    $\begingroup$ No, you can't just "say" an operation has some amortized cost without fixing which kind of sequences you want to talk about. The amortized costs are the end result. It's really about the total cost of this sequence, which you may then divide by the number of operations to get "amortized costs" for single operations. Without a sequence, there's no total, and nothing to divide. $\endgroup$ – Raphael Jun 22 '16 at 22:01
3
$\begingroup$

First, for a bit of clarifying terminology: rather than proving an amortized insertion cost of $O(\lg n)$ and an amortized deletion cost of $O(1)$, you are using those amortized costs to prove something about the total cost of a sequence of insertions and deletions, starting with an empty heap. This might be a subtle distinction, but it is fairly important (at least to me). If you allow yourself to start from a non-empty heap, you would also need to allow yourself to start with a $\Theta(n \lg n)$ potential, or else the deletion amortized cost won't work. Or, if you were to add in an operation for the worst-case linear time build-heap operation, you would also need for that linear time operation to add $\Theta(n \lg n)$ to the potential function.

To use your desired amortized runtimes, each insertion has to prepay for a deletion to come later. So, for instance, when inserting into a heap of size $n$, you can pay for the actual insertion $O(\lg n)$, but your amortized cost will pay that plus an additional $O(\lg n)$ for the worst-case runtime of deleting from a heap of size $n+1$. Now, every time you delete from a non-empty heap? That deletion's actual cost has already been prepayed by a previous insertion's amortized cost. It costs 0 (amortized) to delete. The only deletions that you still need to pay for are the ones from an empty heap, for when your deletions outnumber prior insertions, and those cost $O(1)$.

While these bounds are fine to use for a proof of efficiency for a sequence of insertions and deletions, they are slightly odd, in that in real life, the deletions generally take expected $\Theta(\lg n)$ time, and insertions take expected $\Theta(1)$ time, for some reasonable definitions of operating on a random heap of size $n$.

While I have presented this in terms of "prepaying" (or the accounting method), in this case, just writing it down as a more formal equation directly transforms it into the potential function method. You will be able to prove that the potential of a heap with $n$ elements is at least $\sum_{i=1}^n f(i)$ where $f(i)$ is the worst-case price to delete the min item from a heap if $i$ elements. You already start your question with a given $O(\lg i)$ bound on $f(i)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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