《剑指offer》-数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

最开始的思路就是用map或者set存储。习惯写python就想直接用median的key去访问median，但是C++ STL的map或者set没有key这个东西，如果用迭代器那么访问元素复杂度是O（n）

看到很多解法是用两个堆来做，一个最大堆，一个最小堆，一开始不理解。后来发现这样的好处是把数据总体切分为两部分，一部分（最大堆）所有元素都比另一部分（最小堆）小。然后当有新元素需要insert的时候，根据现有元素总数奇偶，决定先压入哪个堆，然后弹出一个元素，弹出元素放入另一个堆。

最后的答案处理，根据元素总数奇偶，决定从两个堆分别取还是从特定的那个取。

class Solution{
public:
    void Insert(int num){
        if (maxS.size() == minS.size()){
            maxS.insert(num);
            minS.insert(*maxS.begin());
            maxS.erase(maxS.begin());
        }
        else{
            minS.insert(num);
            maxS.insert(*minS.begin());
            minS.erase(minS.begin());
        }
    }

    double GetMedian(){
        int num = maxS.size() + minS.size();

        double median;
        if ((num&1)==1){
            median = *minS.begin();
        }
        else{
            median = (*maxS.begin() + *minS.begin()) / 2.0;
        }
        return median;
    }
private:
    multiset<int, greater<int> > maxS;
    multiset<int, less<int> > minS;
};