数据流中位数

思路

维护两个优先队列：小根堆 & 大根堆

小根堆：存放右半边最小值元素

大根堆：存饭左半边最大值元素

保持两个优先队列大小始终相等或相差 1

添加元素：如果需要加入大根堆中，则需要先插入小根堆，然后弹出小根堆顶元素加入大根堆中，这样才可以保证maxQ 中所有元素 < minQ 中的所有元素；反之亦然

返回中位数：如果两个优先队列大小相等，则返回堆顶元素和的平均值；如果不相等，则返回元素值更多的堆顶

实现

class MedianFinder {
    // 小根堆：存放右半边大值元素
    Queue<Integer> minQ;
    // 大根堆：存放左半边小值元素
    Queue<Integer> maxQ;

    public MedianFinder() {
        minQ = new PriorityQueue<>();
        maxQ = new PriorityQueue<>((o1, o2) -> (o2 - o1));
    }
    
    public void addNum(int num) {
        // 始终保持 maxQ 中所有元素 < minQ 中的所有元素
        if (maxQ.size() <= minQ.size()) {
            minQ.offer(num);
            maxQ.offer(minQ.poll());
        } else {
            maxQ.offer(num);
            minQ.offer(maxQ.poll());
        }
    }
    
    public double findMedian() {
        if (minQ.size() == maxQ.size()) return (minQ.peek() + maxQ.peek()) / 2.0;
        return minQ.size() > maxQ.size() ? minQ.peek() : maxQ.peek();
    }
}