每天一道剑指offer-数据流的中位数

public void Insert(Integer num) {

}

public Double GetMedian() {

}

public class Solution {

    //小根堆、大根堆
    PriorityQueue<Integer> minHeap = new PriorityQueue(new MinRootHeadComparator());
    PriorityQueue<Integer> maxHeap = new PriorityQueue(new MaxRootHeadComparator());
    int count = 0;

    class MaxRootHeadComparator implements Comparator<Integer>{
        //返回值大于0则认为逻辑上i2大于i1（无关对象包装的数值）
        public int compare(Integer i1, Integer i2){
            return i2.intValue() - i1.intValue();
        }
    }

    class MinRootHeadComparator implements Comparator<Integer>{
        public int compare(Integer i1, Integer i2){
            return i1.intValue() - i2.intValue();
        }
    }

    public void Insert(Integer num) {
        count++;//当前这个数是第几个进来的
        //编号是奇数就放入小根堆（右半边），否则放入大根堆
        if(count % 2 != 0){
            //如果要放入右半边的数比左半边的最大值要小则需调整左半边的最大值放入右半边并将当前这个数放入左半边，这样才能保证右半边的数都比左半边的大
            if(maxHeap.size() > 0 && num < maxHeap.peek()){
                maxHeap.add(num);
                num = maxHeap.poll();
            }
            minHeap.add(num);
        }else{
            if(minHeap.size() > 0 && num > minHeap.peek()){
                minHeap.add(num);
                num = minHeap.poll();
            }
            maxHeap.add(num);
        }
    }

    public Double GetMedian() {
        if(count == 0){
            return 0.0;
        }
        if(count % 2 != 0){
            return minHeap.peek().doubleValue();
        }else{
            return (minHeap.peek().doubleValue() + maxHeap.peek().doubleValue()) / 2;
        }
    }
}