CodingInterview-数据流中的中位数

感觉这道题的复杂程度还是比较高的，参考了书里的内容，利用书中一模一样的思路，完成了程序。

程序的基本思路是将插入的数据等分为两个部分，并且左边部分的所有数字都小于右边部分。堆排序是一个比较方便的办法，它的插入复杂度是 O(logn)，而得到中位数的复杂度是 O(1)，时间效率非常高。具体的思路是左侧使用最大堆来实现，堆顶可以获取左侧部分的最大元素，而右侧使用最小堆实现，堆顶可以获取右侧的最小元素，而最小堆中的元素永远大于最大堆中的元素。

为了保证数据的平均分配，可以在之前插入数据的数目为奇数的时候，就插入到最大堆中，否则就插入到最小堆中。但是如果在插入最小堆的时候发现它比最大堆中的最大元素还要小，说明这个数字应该插入左侧的最大堆中，这时候就需要先把数字插入最大堆中，然后再对最大堆排序，弹出最大堆堆顶的最大元素，插入到最小堆中。

在获取中位数的时候，由于第一个元素插入到最小堆中，所以如果是奇数个元素的话，就获取最小堆堆顶的元素，如果是偶数的话，就获取最大堆和最小堆堆顶的元素并取平均值。

class Solution {
private:
    vector<int> min;
    vector<int> max;
public:
    void Insert(int num)
    {
        //如果是偶数，插入最小堆中
        if(((min.size()+max.size())&1)==0){
            //如果最大堆中有元素，并且要插入的元素比最大堆中的最大的元素小
            if(max.size()>0 && num<max[0]){
                //先将元素放入最大堆中
                max.push_back(num);
                //最大堆排序
                push_heap(max.begin(),max.end(),less<int>());
                //获取最大堆中的最大元素
                num=max[0];
                //最大堆中弹出最大元素
                pop_heap(max.begin(),max.end(),less<int>());
                max.pop_back();
            }
            min.push_back(num);
            push_heap(min.begin(),min.end(),greater<int>());
        }else{
            if(min.size()>0 && num>min[0]){
                min.push_back(num);
                push_heap(min.begin(),min.end(),greater<int>());
                num=min[0];
                pop_heap(min.begin(),min.end(),greater<int>());
                min.pop_back();
            }
            max.push_back(num);
            push_heap(max.begin(),max.end(),less<int>());
        }
    }

    double GetMedian()
    {
        int len=min.size()+max.size();
        if(len==0) return 0.0;
        double median;
        if((len&1)==0){
            median=((double)min[0]+(double)max[0])/2;
        }else{
            median=(double)min[0];
        }
        return median;
    }

};