Consider our binary tree HEAP data structure. Recall that it supports INSERT and EXTRACT_MAX in O(log n)

Fantastic news! We've Found the answer you've been seeking!

Question:

Consider our binary tree HEAP data structure. Recall that it supports INSERT and EXTRACT_MAX in O(log n) worst case time, where n is the number of elements in the PRIORITY QUEUE.

(a) Give a potential function 4) such that the amortized cost of INSERT is O(log n) and the amortized cost of EXTRACT_MAX is O(1) with respect to ϕ. Justify your answer.

(b) Prove that for any constant c, the potential function ϕ(H) = c × size(H) is not a solution to (a).

(c) Consider a sequence of n EXTRACT_MAX operations performed on a heap H that initially contains n elements. Does the fact that the amortized cost of each EXTRACT_MAX operation is O (1) mean that the entire sequence can be processed in 0(n) time? Justify your answer.