【常见面试算法】数据流的中位数

问题

如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

样例
输入：1, 2, 3, 4
输出：1, 1.5, 2, 2.5

解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。

思路

准备一个大根堆、一个小根堆，大根堆维护输入的数字中较小的部分，小根堆维护较大的部分。

轮到第偶数个数时，push进大根堆，并从大根堆poll一个数（这个数当然是大根堆中最大的数）放入小根堆，
轮到第奇数个数是，push进小根堆，并从小根堆poll一个数（这个数当然是小根堆中最小的数）放入大根堆，
以上两步可以保证大根堆的数永远比小根堆多一个。

那么对于每个输入的数，到此为止的中位数为：
若目前已经有奇数个数，大根堆堆顶就是中位数；
是偶数，那么peek两个堆顶，求平均数即为中位数。

class Solution {

    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
        public int compare(Integer o1,Integer o2) {
            return o2 - o1;
        }
    });
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public void insert(Integer num) {
        if (((maxHeap.si***Heap.size()) & 1) == 1) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }

    public Double getMedian() {
        if (((maxHeap.si***Heap.size()) & 1) == 1) {
            return (double)maxHeap.peek();
        } else {
            return (double)(maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }

}