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();
            }
        }

    }