数据流的中位数

---

image.png image.png

使用双pq，一个大顶堆装小于middle的数，一个小顶堆装大于middle的数。大顶堆与小顶堆之间元素个数差不能大于1。（N，N）或（N+1，N）或（N，N+1）

class MedianFinder {
public:
    /** initialize your data structure here. */
    int length;
    priority_queue<int,vector<int>,less<int>>pqbottom;
    priority_queue<int,vector<int>,greater<int>>pqtop;
    MedianFinder() {
        length=0;
    }
    
    void addNum(int num) {
        // N N
        // N N+1 
        // N+1 N
        if(pqbottom.size()==pqtop.size()){
            if(length==0){
                pqbottom.push(num);
                // 统一优先放bottom，这样方便后续为pq空时候的判断
            }
            else if(num>pqbottom.top()){
                pqtop.push(num);
            }else{
                pqbottom.push(num);
            }
        }
        else if(pqbottom.size()>pqtop.size()){
            if(num>pqbottom.top()){
                pqtop.push(num);
            }
            else{
                pqbottom.push(num);
                pqtop.push(pqbottom.top());
                pqbottom.pop();
            }
        }
        else{
            if(num>pqbottom.top()){
                pqtop.push(num);
                pqbottom.push(pqtop.top());
                pqtop.pop();
            }
            else{
                pqbottom.push(num);
            }
        }
        length++;
    }
    
    double findMedian() {
        if(length==0){
            return 0;
        }
        if(length&1){
            if(pqbottom.size()>pqtop.size()){
                return pqbottom.top();
            }
            else{
                return pqtop.top();
            }
        }
        else{
            int m1=pqtop.top();
            int m2=pqbottom.top();
            return double(m1+m2)/2;
        }
    }
};