剑指offer——数据流中的中位数

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

思路：设想，如果是一个排序数组，则中位数是中间的一个数(奇数)或两个数(偶数)。

如上图所示，排序数组，个数是奇数时，中位数是中间的一个数，个数是偶数时，中位数是中间两个数的平均值。也可以这样想，中位数是左边排序数组的最大值，右边排序数组的最小值。既然这样，左右元素是否排序就不重要了，只要保证左边的数值都比右边的数值小就可以了，这样只需要查找到左边的最大值和右边的最小值即可。

找最大值和最小值，用最大堆和最小堆来实现。具体细节在注释里说明了

class Solution {
public:
    void Insert(int num)
    {
        if(((minHeap.size()+maxHeap.size())&1)==0){//当前数字个数是偶数时，最终应该插入到minHeap
            if(maxHeap.size()>0&&num<maxHeap[0]){//挑选maxHeap中最大的元素添加到minHeap中
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(),maxHeap.end(),less<int>());//保持最大堆
                num=maxHeap[0];
                pop_heap(maxHeap.begin(),maxHeap.end(),less<int>());
                maxHeap.pop_back();
            }
            minHeap.push_back(num);
            push_heap(minHeap.begin(),minHeap.end(),greater<int>());
        }else{//当前数字个数是奇数时，最终应该插入到maxHeap中
            if(minHeap.size()>0&&num>minHeap[0]){//挑选minHeap中最小的元素添加到maxHeap中
                minHeap.push_back(num);
                push_heap(minHeap.begin(),minHeap.end(),greater<int>());
                num=minHeap[0];
                pop_heap(minHeap.begin(),minHeap.end(),greater<int>());
                minHeap.pop_back();
            }
            maxHeap.push_back(num);
            push_heap(maxHeap.begin(),maxHeap.end(),less<int>());
        }
    }

    double GetMedian()
    {
        double res;
        if(minHeap.size()+maxHeap.size()<1)
            return 0.0;
        if(((minHeap.size()+maxHeap.size())&1)==1)
            res=minHeap[0];
        else
            res=(minHeap[0]+maxHeap[0])/2.0;//在做除法的时候需要注意，被除数要是浮点数，最终结果才能得到浮点数
        return res;
    }
private:
    vector<int> minHeap;
    vector<int> maxHeap;
};