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

class Solution {
public:
    priority_queue<int,vector<int>,greater<int>> Rmin;//小根堆，用来存放中位数右边的部分
    priority_queue<int> Lmax;//大根堆，用来存放中位数及其左边的部分
    int cn=0;//记录当前放入的数据个数
    void Insert(int num) {
        if(cn%2==0){//当前放了偶数个数据
            //此时如果再放,肯定要放在大根堆中，但是又不知道此时的数据是否小于等于中位数，所以通过小根堆筛选一下
            Rmin.push(num);
            Lmax.push(Rmin.top());Rmin.pop();
        }
        else{//此时已经放了奇数个数据，再放数据肯定要放在小根堆里面，但是又不知道num是否大于中位数，所以通过大根堆筛选一下
            Lmax.push(num);
            Rmin.push(Lmax.top());Lmax.pop();
            
        }
        cn++;
    }
    //如果cn为偶数则中位数为大小根堆的对顶和的平均值
    //如果为奇数，则为大根堆的堆顶
    double GetMedian() {
    if(cn%2==0)
        return double((Lmax.top()+Rmin.top())/2.0);
         else return double(Lmax.top());
    }
   

};