【剑指】73，数据流的中位数（大根堆和小根堆）

我不是女神ヾ 2023-07-17 11:21 25阅读 0赞

**题目描述**

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

思路：  
利用两个堆，一个大根堆一个小根堆。然后插入的时候通过两者的size和顶部的数字进行判断。  
1, 如果大根堆（堆顶为最大值）为空，就将值插入大根堆  
2，如果大根堆不为空，那么我们就判断两堆是不是一样大，如果一样大，判断target和大根堆/小根堆的数据大小比较。如果target>max.top，说明因该加入小根堆。**否则**如果target小了，就应该插入大根堆。  
3，如果大根堆的数量多了，判断顶和target的比较，target大了：插入小根堆；小了，弹出大根堆堆顶到小根堆插入，同时压入target。  
4，如果小根堆数量多了，判断，如果堆顶的数小于target，弹出顶然后压入target，否则，压入大根堆。

代码：

class Solution { 
    public:
        void Insert(int num)
        { 
            if(bigger.empty() )
               {  bigger.push(num);
                    return ;
               }
            if(bigger.size()==little.size())    //说明两堆数量相同，看num大小进堆
               { 
                   if(bigger.top()>=num)
                   { 
                       bigger.push(num);
                   }
                   else
                       little.push(num);
               }
             else if(bigger.size() < little.size())   //大根堆数量较少。应该插入大根堆或弹出小根堆顶插入大根堆，在插入数
               { 
                   if(little.top() > num)
                   { 
                       bigger.push(num);
                   }
                   else
                   { 
                       bigger.push(little.top());
                       little.pop();
                       little.push(num);    //小根堆维护大的数，大根堆维护小的数。
                       
                   }
               }
               else  //大根堆数量多了
               { 
                   if(bigger.top()> num)
                   { 
                       little.push(bigger.top());
                       bigger.pop();
                       bigger.push(num);
                   }
                   else
                       little.push(num);
               }
        }
    //维护了两个堆之后呢，按照大小来、分
        double GetMedian()
        {  
           if(bigger.size() == little.size())
           { 
               return (bigger.top()+little.top())/2.0 ;
           }
           else if(bigger.size()>little.size())
               return bigger.top();
            else
                return little.top();			//返回数较多的一个堆顶。
        }
    private:
        priority_queue< int ,vector<int>,less<int> >  bigger;    //数字大的优先级高，放根部
        priority_queue<int ,vector<int> ,greater<int> > little;    //数字小的优先级高。小根堆
    };