only (c)

2. (10 marks) Consider our binary tree HEAP data structure. Recall that it supports INSERT and EX TRACT MAX in O(log n) worst case time, where n is the number of elements in the PRIORITY QUEUE. (a) Give a potential function such that the amortized cost of INSERT is O(log n) and the amor- tized cost of EXTRACT-MAX is O(1) with respect to . Justify your answer. (b) Prove that for any constant c, the potential function (H)-cx 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 O(n) time? Justify your answer. 2. (10 marks) Consider our binary tree HEAP data structure. Recall that it supports INSERT and EX TRACT MAX in O(log n) worst case time, where n is the number of elements in the PRIORITY QUEUE. (a) Give a potential function such that the amortized cost of INSERT is O(log n) and the amor- tized cost of EXTRACT-MAX is O(1) with respect to . Justify your answer. (b) Prove that for any constant c, the potential function (H)-cx 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 O(n) time? Justify your