第 14 关 | 刷题模板之堆结构：3. 黄金挑战—

1. 数据流中中位数的问题

来看一个有些难度的题目，LeetCode295，中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如:[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

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

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

示例：
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

进阶问题：

1如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？

2如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
分析

这是一道比较难的题目了，如果没专门学过，很难在面试时想到。

中位数的题，我们一般都可以用大顶堆 + 小顶堆来求解，下面我们通过直观的例子解释一下怎么做。

小顶堆（minHeap）：存储所有元素中较大的一半，堆顶存储的是其中最小的数。

大顶堆（maxHeap）：存储所有元素中较小的一半，堆顶存储的是其中最大的数。

相当于，把所有元素分成了大和小两半，而我们计算中位数，只需要大的那半的最小值和小的那半的最大值即可。

比如，我们依次添加 [1, 2, 3, 4, 5]，砍成两半之后为 [1, 2] 和 [3, 4, 5]，我们只要能快速的找到 2 和 3 即可。

下面看看使用两个堆它们是怎么变化的：

添加 1，进入到 minHeap 中，中位数为 1：
添加 2，它比 minHeap 堆顶元素 1 大，进入minHeap，同时，minHeap 中元素超过了所有元素总和的一半，所以，要平衡一下，分一个给 maxHeap，中位数为 (1 + 2) / 2.0 = 1.5 ：
添加 3，它比 minHeap 堆顶元素 2 大，进入 minHeap，中位数为 2： 2添加 4，它比 minHeap 堆顶元素 2 大，进入minHeap，同时，minHeap 中元素超过了所有元素总和的一半，所以，要平衡一下，分一个给 maxHeap，中位数为 (2 + 3) / 2.0 = 2.5：
添加 5，它比 minHeap 堆顶元素 3 大，进入minHeap，中位数为 3：

Java中的堆（即优先级队列）是使用完全二叉树实现的，我们这里的图也是以完全二叉树为例。

理解了上述的过程，看代码就比较简单了，但是实现起来还是挺麻烦的，所以我们理解一下就好了。

class MedianFinder {
    // 小顶堆存储的是比较大的元素，堆顶是其中的最小值
    PriorityQueue<Integer> minHeap;
    // 大顶堆存储的是比较小的元素，堆顶是其中的最大值
    PriorityQueue<Integer> maxHeap;

    /** initialize your data structure here. */
    public MedianFinder() {
        this.minHeap = new PriorityQueue<>();
        this.maxHeap = new PriorityQueue<>((a, b) -> b - a);
    }
    
    public void addNum(int num) {
        // 小顶堆存储的是比较大的元素，num比较大元素中最小的还大，所以，进入minHeap
        if (minHeap.isEmpty() || num > minHeap.peek()) {
            minHeap.offer(num);
            // 如果minHeap比maxHeap多2个元素，就平衡一下
            if (minHeap.size() - maxHeap.size() > 1) {
                maxHeap.offer(minHeap.poll());
            }
        } else {
            maxHeap.offer(num);
            // 这样可以保证多的那个元素肯定在minHeap
            if (maxHeap.size() - minHeap.size() > 0) {
                minHeap.offer(maxHeap.poll());
            }
        }
    }
    
    public double findMedian() {
        if( minHeap.size() > maxHeap.size() ){
           return minHeap.peek();
        }else if(minHeap.size() < maxHeap.size() ) {
           return maxHeap.peek();
        }else{
           return ((minHeap.peek()+maxHeap.peek())/2.0;
        } 
    }
}

因为C++和Python里没找到提供的堆结构，需要自己构造，因此我们暂时不提供，感兴趣的同学，可以自行研究一下。

第 14 关 | 刷题模板之堆结构：3. 黄金挑战——数据流的中位数-灵析社区

1. 数据流中中位数的问题