A median priority queue. Given a set of keys, a median key is a key in the "middle" when the keys are sorted. When the number of keys is odd, the middle key is unique. However, when the number of keys is even, there are two middle keys. We call on the lower median key and the other the upper median key. For example, if the keys are {3, 8, 2, 10,5,9), then the lower median key is 5 while the upper median key is 8.
For this problem, we wish to implement the MedianPQADT that supports the following methods in O(logn) time:
Insert Item(k, e), RemoveLower Median(), Remove UpperMedian().
When n is even, the items to return for RemoveLowerMedian() and RemoveUpper Me dian() are obvious. When n is odd, let these methods simply return the item with the median key.
Our implementation involves two heaps -a max-heap H, and a min-heap Hr. It always maintains the property that contains the [n/2 smallest keys and HR contains the [n/2] largest keys.
(a1) Assume your current set of items are stored using the two-heap im- plementation with the said property. Write a pseudocode for the three methods Insertitem(k, e), RemoveLowerMedian(), Remove Upper Median().
(a2) Briefly argue why the running times of your pseudocodes for the three methods is O(logn).
(b) Starting with an empty two-heap, do six Insertitem with keys 6, 5, 4, 3, 2, 1. Draw what the heaps look like at the end of each insertion step. Then apply RemoveLower Median() and draw the tree at the end of this step.