数据流中的中位数

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof

题解

既然是中位数，容易想到两种解法——快速排序和堆排序。

因为是数据流，数据是一个个放的，因此快速排序每一次插入都排序一次是对资源的浪费。这时，我们将数据分为两半，小的一半用大顶堆维护，大的一半用小顶堆维护，大顶堆最大和小顶堆最小自然是中位数了。这样每次插入只有O(logn)的时间复杂度

public class MedianFinder {
    Queue<Integer> queueA;
    Queue<Integer> queueB;

    /** initialize your data structure here. */
    public MedianFinder() {
        //大顶堆，保存小的一半
        queueA = new PriorityQueue<>((i1, i2) -> i2 - i1);
        //小顶堆，保存大的一半
        queueB = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (queueA.size() != queueB.size()) {
            queueA.add(num);
            queueB.add(queueA.poll());
        }
        else {
            queueB.add(num);
            queueA.add(queueA.poll());
        }
    }

    public double findMedian() {
        if (queueA.size() == 0) return 0.0;
        return queueA.size() != queueB.size() ? queueA.peek() : (queueB.peek() - queueA.peek()) / 2.0 + queueA.peek();
    }
}