题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

题解

将所有数据分为两半，分别放入一个最大堆和一个最小堆中。最大堆用来存较小的数，最小堆用来存较大的数。这时候中位数就是最大堆的根节点和最小根的根节点的平均数。

这种方法一个最关键的点是：在每次插入数据时，不能直接插入，而是需要取另一个堆的根节点进行插入。这样，每次插入最小堆的是当前最大堆中最大的元素，每次插入最大堆的是当前最小堆中最小的元素，这样才能保证最大堆中的值全部小于最小堆中的值。

PriorityQueue<Integer> minHeap;
PriorityQueue<Integer> maxHeap;

Solution() {
    minHeap = new PriorityQueue<>();
    maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });
}

public void Insert(Integer num) {
    if (minHeap.size() == maxHeap.size()) {
        minHeap.offer(num);
        if (!minHeap.isEmpty()) maxHeap.offer(minHeap.poll());
    }
    else {
        maxHeap.offer(num);
        if (!maxHeap.isEmpty()) minHeap.offer(maxHeap.poll());
    }
}

public Double GetMedian() {
    if (minHeap.isEmpty() && maxHeap.isEmpty())
        return 0.0;
    if (!minHeap.isEmpty() && !maxHeap.isEmpty() && minHeap.size() == maxHeap.size())
        return (double) (minHeap.peek() + maxHeap.peek()) / 2;
    else if (!maxHeap.isEmpty())
        return (double) maxHeap.peek();
    else return 0.0;
}