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

#include <algorithm>
class Solution {
// 官解三
// 使用堆
public:
    #define SCD static_cast<double>
    priority_queue<int> min_q; // 大顶堆 存储前面的部分  此处规定长度大于等于后面的部分 相差1
    priority_queue<int, vector<int>, greater<int>> max_q; // 小顶堆

    void Insert(int num) {

        //先加入前半部分
        min_q.push(num);
        max_q.push(min_q.top()); // 自动排序后 把前面的最大值 插入到后半部分
        min_q.pop();

        // 刷新两者的数量 按照规定前面的要不小于后面
        if(min_q.size()<max_q.size())
        {   //否则就平衡下
            min_q.push(max_q.top());
            max_q.pop();
        }
        
    }

    double GetMedian() { 
        double ans;
        if(min_q.size() == max_q.size())
        {
            ans = (min_q.top() + max_q.top())/2.;
        }
        else
        {
            ans = double(min_q.top());
            
        }
        return ans;
    
    }

};

使用两个堆 还是挺巧妙地