跟着姚桑学算法-数据流中的中位数

题. 数据流中的中位数

如何得到一个数据流中的中位数？

如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。

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

数据范围
数据流中读入的数据总数 [1,1000]。

样例

输入：1, 2, 3, 4

输出：1,1.5,2,2.5

解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。

【题解】-- 大根堆、小根堆

在交换2个堆的元素的时候，一定要 先判断上面的小根堆中有没有元素。 上面的小根堆中 没有元素是不能交换的。

小根堆没有元素，就把大根堆中的top放到小根堆中。

复杂度分析：

每个数据流中的数据在插入后，需要常数次数量的堆调整也就是大概O(clog(n/2)) = O(logn)的时间复杂度。
总时间复杂度O(logn)

C++代码实现：

#include <queue>
using namespace std;
class Solution {
public:
    priority_queue<int> maxHeap;
    priority_queue<int> minHeap;
    void insert(int num){
        if(!minHeap.empty() && num > -minHeap.top()){
            maxHeap.push(-minHeap.top());
            minHeap.pop();
            minHeap.push(-num);
        }else{
            maxHeap.push(num);
        }

        if(maxHeap.size() >= minHeap.size() + 2){
            minHeap.push(-maxHeap.top());
            maxHeap.pop();
        }
    }

    double getMedian(){
        return maxHeap.size() == minHeap.size()? (maxHeap.top()-minHeap.top()) / 2.0 : maxHeap.top();
    }
};