Describe how to add the methods \mathtt{sample()}sample() and \mathtt{delRandom()}delRandom() to our binary heap implementation. The two methods return a key that is chosen uniformly at random among the remaining keys, with the latter method also removing that key. The \mathtt{sample()}sample() method should take constant time; the \mathtt{delRandom()}delRandom() method should take logarithmic time. Do not worry about resizing the underlying array.
public class PriorityQueue {
/*
Question 1
Dynamic median.
Design a data type that supports insert in logarithmic time, find-the-median in constant time, and remove-the-median in logarithmic time.
*/
class MediaHeap {
private MaxPQ<Integer> left;
private MinPQ<Integer> right;
private int L;
private int R;
MediaHeap() {
left = new MaxPQ<Integer>();
right = new MinPQ<Integer>();
}
public double findMedian() {
int L = left.size();
int R = right.size();
if (L == R)
return ((double)left.max() + (double)right.min()) / 2;
else if (L > R)
return left.max();
else
return right.min();
}
public void insert(int key) {
double median = findMedian();
int L = left.size();
int R = right.size();
if (key <= median) {
left.insert(key);
if (L - R > 1)
right.insert(left.delMax());
}
else {
right.insert(key);
if (R - L > 1)
left.insert(right.delMin());
}
}
public void removeMedian() {
int L = left.size();
int R = right.size();
if (L > R) {
left.delMax();
}
else {
right.delMin();
}
}
}