题解 | 数据流中的中位数

class Solution {
public:
    priority_queue<int> maxHeap;                             // 左半：最大堆,左半掌管小的
    priority_queue<int, vector<int>, greater<int>> minHeap; // 右半：最小堆，右半掌管大的
    void Insert(int num) {
        if(maxHeap.size()==0)
        {
            maxHeap.push(num);
            return;
        }
        if(!maxHeap.empty()&&num>maxHeap.top())
        {
             minHeap.push(num);
        }
        else 
        { 
             maxHeap.push(num);
        }
        if(!maxHeap.empty() && !minHeap.empty()&&maxHeap.top()>minHeap.top())
        {
            double templeft=maxHeap.top();
            maxHeap.pop();
            double tempright=minHeap.top();
            minHeap.pop();
            maxHeap.push(tempright);
            minHeap.push(templeft);
        }
        if(maxHeap.size()>minHeap.size()+1)//数目不平衡，要保证左半的数目小于等于右半的数目+1
        {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
        if(maxHeap.size()<minHeap.size())
        {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    double GetMedian() { 
     if(maxHeap.size()==minHeap.size()&&maxHeap.size()!=0)
     {
        return (maxHeap.top()+minHeap.top())/2.0;
     }
     else 
     {
        return maxHeap.top();
     }
     return 0;
    }

};