题解 | #数据流中的中位数#

将当前序列维护为 两个堆，一个大根堆，一个小根堆(初始化一个大根堆，存中位数左边的数据，一个小根堆，存中位数右边的数据)，则 中位数 一定在 大根堆 和 小根堆的堆顶 产生。确保 大根堆 中元素个数比 小根堆 元素个数多一个，每次有新元素进入时，先放入 大根堆中，这时比较 大根堆的堆顶和小根堆的堆顶，如果出现 大根堆的堆顶元素比小根堆的堆顶元素大，就交换这两个堆顶元素，由于每次都是将元素放入 大根堆，就可能会出现 大根堆元素个数比 小根堆 元素个数多一个以上，那么就将 大根堆的一个元素 转移到小根堆上。

class Solution {
public:
    //大根堆
    priority_queue<int> max_heap;
    //小根堆
    priority_queue<int,vector<int>,greater<int>> min_heap;

    void Insert(int num) {
         max_heap.push(num);

        //如果大根堆的堆顶元素比小根堆的堆顶元素大，就交换
        if(!min_heap.empty()&&max_heap.top()>min_heap.top())
        {
            int maxV=max_heap.top();
            int minV=min_heap.top();

            max_heap.pop();
            max_heap.push(minV);
            min_heap.pop();
            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();
        }
        //一定要使用浮点数运算
        return (max_heap.top()+min_heap.top())/2.0;
    }

};