[leetCode]剑指 Offer 41. 数据流中的中位数

最大堆，最小堆

 由于需要使用一个数据容器保存从数据流中得到的数据，那么对该容器插入数据与读取数据的时间复杂度有一定要求。
 假设数据在容器中已排序，那么使用两个指针即可得到中位数，当数据量为奇数时p1,p2指向同一个数据。

 如果数据量为偶数，p1指向左边最大数，p2指向右边最小数。

因此可以将数据分为两部分：

• 左半部分
• 右半部分

左半部分应小于等于右半部分。由于需要快速找到左半部分的最大数与右半部分的最小数，可以想到使用最大堆与最小堆。由于要保证左右两部分数据量之差不超过1，所以可以在数据总量为偶数时将新数据插入最小堆，数据总量为奇数时将数据插入最大堆。
 如果新插入最小堆的数据比最大堆的最大数据要小。因为最小堆数据要大于最大堆数据，所以需要新数据插入最大堆，将最大堆的最大数据插入最小堆。同理新插入最大堆的数据大于最小堆最小数据时，应将新数据插入最小堆，将最小堆最小数据插入最大堆。
 代码如下：

class MedianFinder {

    private PriorityQueue<Integer> minPQ;

    private PriorityQueue<Integer> maxPQ;

    /** initialize your data structure here. */
    public MedianFinder() {
        this.minPQ = new PriorityQueue<>(600);//初始化容量
        this.maxPQ = new PriorityQueue<>(600,new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
    }
    
    public void addNum(int num) {
        if(((minPQ.size() + maxPQ.size()) & 1) == 0){//数据总量为偶数，把新数据插入最小堆
            if(maxPQ.size() > 0 && num < maxPQ.peek()){//最小堆的数据>最大堆数据
                maxPQ.offer(num);//新数据插入最大堆
                num = maxPQ.poll();
            }
            minPQ.offer(num);//取出最大堆最大数据加入最小堆
        }else{//数据总量为奇数插入最大堆
            if(minPQ.size() > 0 && num > minPQ.peek()){
                minPQ.offer(num);
                num = minPQ.poll();
            }
            maxPQ.offer(num);
        }
    }
    
    public double findMedian() {
        int size = minPQ.size() + maxPQ.size();
        if(size == 0)
            throw new RuntimeException("No numbers are available");
        double median = 0;
        if((size & 1) == 1)
            median = minPQ.peek();
        else
            median = (minPQ.peek() + maxPQ.peek())/2.0;
        return median;
    }
}

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