[数据结构与算法]295. 数据流的中位数

295. 数据流的中位数

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

例如，

[2,3,4] 的中位数是 3

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

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

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

这题难就难在，如何在较低的时间复杂度里面实现findMedian。

• 如果把所有数据存入数组，那么每次插入都需要将元素挪动，时间复杂度至少 O(n)。
• 使用二叉搜索树倒不是不行，需要每个节点维护当前这棵树有多少节点。这样也会导致add和find操作都是O(logn)，主要还是实现起来会麻烦一些，因为这样的二叉搜索树你还得自己实现一个呢，需要实现二叉搜索树的插入和按rank查找操作。当然，极端情况下，二叉搜索树也可能退化成链表，那复杂度也是O(n)。

这个问题的解法非常巧妙，我是没想到。这里是看了labuladong的解题思路，自己回放一遍。建议直接看labuladong的原文。

实现的思路是使用两个优先级队列，一个是大根堆，一个是小根堆。要求满足以下条件：

• 大根堆所有的元素小于等于 小根堆所有元素，即大根堆堆顶元素小于小根堆堆顶元素
• 如果大根堆元素和小根堆元素个数相等，则插入时，优先插入大根堆；否则插入小根堆。

如果所有元素满足以上两个条件，那么中位数(findMedian函数逻辑）就是：如果大根堆元素多，就大根堆堆顶，否则就是两个堆顶元素取平均值。

为了保证以上两个条件，在插入元素（addNum函数逻辑）时，需要进行以下操作：

• 首先根据大根堆和小根堆元素判断应该插入大根堆还是小根堆，这样满足条件2
• 插入大根堆，则需要先插入小根堆，再将小根堆堆顶元素插入大根堆；反之，亦然，这样才能保证条件1成立

代码实现

class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int> maxHeap;// 默认大根堆
    priority_queue<int,vector<int>,greater<int>>minHeap;// 小根堆
    /*
    	实现的思路是使用两个优先级队列，一个是大根堆，一个是小根堆。要求满足以下条件：

        - 大根堆所有的元素小于等于 小根堆所有元素，即大根堆堆顶元素小于小根堆堆顶元素
        - 如果大根堆元素和小根堆元素个数相等，则插入时，优先插入大根堆；否则插入小根堆。
    
    */
    
    MedianFinder() {
		
    }
    
    void addNum(int num) {
        /*
        - 首先根据大根堆和小根堆元素判断应该插入大根堆还是小根堆，这样满足条件2
		 - 插入大根堆，则需要先插入小根堆，再将小根堆堆顶元素插入大根堆；反之，亦然，这样才能保证条件1成立
        */
		if(maxHeap.size()==minHeap.size()){
            // 优先插入大根堆
            minHeap.push(num);
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }else{
            maxHeap.push(num);
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }
    
    double findMedian() {
        /*
        如果大根堆元素多，就大根堆堆顶，否则就是两个堆顶元素取平均值。
        */
        if(minHeap.size()==maxHeap.size()){
            return (minHeap.top()+maxHeap.top())/2.0;
        } else{
            return maxHeap.top();
        }

    }
};