剑指offer. 41 数据流中的中位数 （重要）

题目描述：

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

解题思路：

用两个堆，一个大顶堆来维持前1半的 数，一个小顶堆维持后一半的数

规则：
1. 为了维持有序性，当加新的数时，如果数小于等于 大顶堆的top时，加大顶堆，否则加小顶堆 (第1个数，无脑加大顶堆)
2. 为了维持 各自一半，两个堆的size之差不能超过1，因此每加完一个数，检查一下，假如大于1了，那肯定是2，那就从size大的pop一个出来压入size小的那个堆
3. 查询当前中位数： 假如 size 一样，则中位数为 两个top 的和的一半
假如 size 不一样，那肯定是差1，那size大的那个top 就是中位数 

代码：

class Solution {
public:
    void Insert(int num)
    {
       if(max_pq.empty()){
		   max_pq.push(num);
		   return;
	   }
	   if(num<=max_pq.top()){
		   max_pq.push(num);
	   }
	   else{
		   min_pq.push(num);
	   }
	   
	   if(abs(max_pq.size()-min_pq.size())>1){
		   if(max_pq.size()>min_pq.size()){
			   min_pq.push(max_pq.top());
			   max_pq.pop();
		   }
		   else{
			   max_pq.push(min_pq.top());
			   min_pq.pop();
		   }
	   }
	      
    }

    double GetMedian()
    { 
		if(max_pq.size()==min_pq.size()) return ((double)(max_pq.top()+min_pq.top()))/2;  // 注意 返回类型要求是double
		else return max_pq.size()>min_pq.size()?max_pq.top():min_pq.top();
    }
	priority_queue<int> max_pq;
	priority_queue<int,vector<int>,greater<int>> min_pq;
};

---