Question

Consider an ordinary binary heap data structure with n elements that supports the instructions Insert and Extract-Min in O(log n) worst- case time. Give a potential function Φ such that the amortized cost of Insert is O(log n) and the amortized cost of Extract-Min is O(1), and show that it works.

Answer 1

Answer:

It has been proved from the explanation below that the amortized cost of Insert is O(log n) and the amortized cost of Extract-Min is O(1),

Step-by-step explanation:

First of all, let's look at what "Extra-min" does;

It does the following ;

- Extract the root, (O1) actual time

- Replaces it with the last element x in the heap and repair the heap down or up.

- It takes O (Logn) time which is the depth of the heap.

Now, to get O(1) amortized time for extra-min, the last element "x" must have enough potential for repairing the heap and this potential must be in order of its depth.

Since we have K elements and so the weight of the kth element is WK in the heap as it's depth. So we can say;

WK = log k - - - - - - - - - eq (1)

Thus, the potential function Φ of the heap Hn for the n elements can be defined as ΦHn = Σ(WK) for k = 1 up till n. And so ΦHn will surely be greater than 0.

Thus; ΦHn = n(Logn)

Now let's check for insert ;

- pay actual cost of insert (logn)

-raise potential of the new elements

Now, using extra-min; O(1) amortized. To repair the heap, we'll use the potential of log(n) for the last element x as mentioned earlier.

In summary, when we use insert, potential increases and this can be afforded by paying insert more while when extra-min, potential decreases by a right moment of the cost of repairing.

Thus, we clearly see that Insert is O(log n) amortized and Extract-Min is O(1) amortized.