数据流中位数

数据流中位数

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。

分析：

我们必然需要有序数据结构，本题的核心思路是使用两个优先级队列。使用一个大顶堆和一个小顶堆将有序队列分成两半。

梯形虽然是小顶堆，但其中的元素是较大的，我们称其为large，倒三角虽然是大顶堆，但是其中元素较小，我们称其为small

1. 两个堆中的元素之差不能超过 1。

2. large堆的堆顶元素要大于等于small堆的堆顶元素。(见addNum技巧)

   想要往large里添加元素，不能直接添加，而是要先往small里添加，然后再把small的堆顶元素加到large中；向small中添加元素同理。

class MedianFinder {
    private PriorityQueue<Integer> large;
    private PriorityQueue<Integer> small;

    public MedianFinder() {
        // 小顶堆
        large = new PriorityQueue<>();
        // 大顶堆
        small = new PriorityQueue<>((a, b) -> {
            return b - a;
        });
    }

    public double findMedian() {
        // 如果元素不一样多，多的那个堆的堆顶元素就是中位数
        if (large.size() < small.size()) {
            return small.peek();
        } else if (large.size() > small.size()) {
            return large.peek();
        }
        // 如果元素一样多，两个堆堆顶元素的平均数是中位数
        return (large.peek() + small.peek()) / 2.0;
    }

    // 正确的代码实现
		public void addNum(int num) {
    		if (small.size() >= large.size()) {
        		small.offer(num);
        		large.offer(small.poll());
    		} else {
        		large.offer(num);
        		small.offer(large.poll());
    		}
    }
}