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.
