从数据流中快速查找中位数

这题的思路就是维护两个堆，一个大根堆一个小根堆，将数据加入到这两个堆中，这样从两个堆的堆顶就可以获取整个数据的中位数。
C++中的priority_queue 默认是以大根堆存储的，也就是说，堆顶是堆中最大的元素。如果要定义小根堆，那么就得自己写一个仿函数。具体看代码注释

class MedianFinder 
{
    
    class cmp
    {
    
        public:
            bool operator()(double a,double b)
            {
    
                return a>b;//返回true时，优先级会更低，也就是a的优先级会低于b，a会往堆底调整
            }
     };  
    priority_queue<double,vector<double>,cmp> Small;//构建小顶堆
    priority_queue<double,vector<double>> Large;//构建大顶堆
public:
    MedianFinder() 
    {
    
        
    }
    
    void addNum(int num) 
    {
    
        if(Large.size()==0 && Small.size()==0)//第一个加入的元素默认先放在Large
        {
    
            Large.push(num);
            return;
        }
        
        if(num<=Large.top())//如果num小于Large的堆顶，那么num就放入Large堆中
        {
    
            Large.push(num);
            cout<< num<<"push to large"<<endl;
        }
        else//若num大于Large堆顶，也就是比Large最大的大，那么放入Small中
        {
    
            Small.push(num);
            cout<< num<<"push to small"<<endl;
        }
        
        //如果两个堆的数量之差为2，那么需要重新调整一下大小，把大的那个堆顶元素放在小的那个堆上
        //为什么差为2的时候调整？因为这样就可以保证调整完后，两个堆数量一致。(3:1)->(2:2)这样的
        if(Large.size()-Small.size()==2)
        {
    
            int temp=Large.top();
            Large.pop();
            Small.push(temp);
            return;
        }
        
        if(Small.size()-Large.size()==2)
        {
    
            int temp=Small.top();
            Small.pop();
            Large.push(temp);
            return;
        }
    }
    
    double findMedian() 
    {
    
        if(Small.size()>Large.size())
            return Small.top();
        else if(Small.size()<Large.size())
            return Large.top(); 
        
       return (Small.top()+Large.top())/2; 
    }
};