剑指offer_12_数据流中的中位数

// 优先队列默认是小顶堆
staticPriorityQueue<Integer> minHeap = new PriorityQueue();
// 重写比较器让他变成大顶堆
staticPriorityQueue<Integer> maxHeap = new PriorityQueue((o1,o2)->(Integer)o2 - (Integer)o1);
// 用于计数，让俩个堆插入数据时持平
staticint count = 0;
public static void add(Integer number) {

    if (count % 2 == 0) {
        // 为了使小顶堆里的数据都比大顶堆的数据大 每次插入都要进行操作
        minHeap.add(number);
        // 加入的元素为基数时大顶堆 要多一个元素 根就是中位数了
        maxHeap.add(minHeap.poll());
    } else {
        maxHeap.add(number);
        minHeap.add(maxHeap.poll());
    }
    count ++;

}
public static double getMedian() {
    if (count % 2 == 0) {
        return (minHeap.peek() +maxHeap.peek()) / 2.0;
    } else {
        // 为计数时大顶堆的根就是中位数 因为大顶堆多一个元素
        return (double)maxHeap.peek();
    }
}

public static void main(String[] args) {
    add(1);
    add(2);
    System.out.println(getMedian()); // 1.5
    add(3);
    System.out.println(getMedian()); // 2.0
}