剑指offer 42- 数据流中的中位数

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

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

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

输入：1, 2, 3, 4

输出：1,1.5,2,2.5

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

分析：

把所有的数维护成两个集合
小根堆存比较大的那一半数；大根堆存的是比较小的那一半数、
大根堆的堆顶和小根堆的堆底就是序列的比较小的两个数
人为规定：如果是奇数个，大根堆比小根堆多一个
每次插入，就先插入max_heap里
如果大根堆的数大于小根堆的数，就交换一下数
如果大根堆的数比小根堆的数多一个以上，就把大根堆的数弹出一个放到小根堆
时间复杂度：

class Solution {
public:
    /*
    把所有的数维护成两个集合
    小根堆存比较大的那一半数；大根堆存的是比较小的那一半数、
    大根堆的堆顶和小根堆的堆底就是序列的比较小的两个数
    人为规定：如果是奇数个，大根堆比小根堆多一个
    每次插入，就先插入max_heap里
    如果大根堆的数大于小根堆的数，就交换一下数
    如果大根堆的数比小根堆的数多一个以上，就把大根堆的数弹出一个放到小根堆
    */
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    
    void insert(int num){
        //每次插入，就先插入max_heap里
        max_heap.push(num);
        //如果大根堆的数大于小根堆的数，就交换一下数
        if(min_heap.size() && max_heap.top() > min_heap.top()) {
            auto maxv = max_heap.top(), minv = min_heap.top();
            max_heap.pop(), min_heap.pop();
            max_heap.push(minv), min_heap.push(maxv);
        }
        //如果大根堆的数比小根堆的数多一个以上，就把大根堆的数弹出一个放到小根堆
        if(max_heap.size() > min_heap.size()+1) {
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }

    double getMedian(){
        if((max_heap.size() + min_heap.size()) & 1) return max_heap.top();
        else return (max_heap.top() + min_heap.top())/2.0;
    }
};