295. Find Median from Data Strea

考到了，完全没反应过来。这里是用两个heap来保存stream里的数；max heap保存小的那一半，min heap保存大的那一半数。这样的话，当两个heap里的数个数相同的时候，（maxPQ.peek + minPQ.peek）/2 就是median; 而且始终保持maxPQ的个数等于或比minPQ 的个数大于一，这样的话maxPQ.peek()就是两者个数不相等时的median

class MedianFinder {
    PriorityQueue<Integer> minPQ;
    PriorityQueue<Integer> maxPQ;
    /** initialize your data structure here. */
    public MedianFinder() {
        //keep the larger half of the integer stream
        minPQ = new PriorityQueue<>();
        //keep the smaller half of the integer stream
        maxPQ = new PriorityQueue<>(1000, Collections.reverseOrder());
    }
    
    public void addNum(int num) {
        maxPQ.add(num);
        minPQ.add(maxPQ.poll());
        if (maxPQ.size() < minPQ.size()){
            maxPQ.offer(minPQ.poll());
        }
    }
    
    public double findMedian() {
        if (maxPQ.size() == minPQ.size()){
            return (maxPQ.peek() + minPQ.peek()) / 2.0;
        } else {
            return maxPQ.peek();
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */