multiset c++实现

法一：用Multiset做的，因为它有个自动排序功能

class Solution {
public:
    void Insert(int num)
    {
        stream.insert(num);
    }

    double GetMedian()
    {
        double res = 0.0;
        unsigned int size = stream.size();

        multiset<int>::iterator it = stream.begin();
        unsigned int cnt = size / 2;
        while(cnt){
            --cnt;
            ++it;
        }
        if(size % 2 == 0)
            res = (double)(*it + *(--it)) / 2;
        else
            res = *it;
        return res;
    }
private:
    multiset<int> stream;
};

法二：用最大堆最小堆做

class Solution {
private:
    int size = 0;
    priority_queue<int, vector<int>, less<int>> max;
    priority_queue<int, vector<int>, greater<int>> min;

public: //用一个最大堆和一个最小堆做
    void Insert(int num)
    {
        ++size;
        //偶数时，放入最小堆，奇数时，放入最大堆
        //如果num为偶数，且比最小堆的top还大，则先入最小堆，再把堆顶入最大堆；num奇数同理
        if(size & 1){
            if(!min.empty() && num > min.top()){
                min.push(num);
                num = min.top();
                min.pop();
            }
            max.push(num);
        }
        else{
            if(!max.empty() && num < max.top()){
                max.push(num);
                num = max.top();
                max.pop();
            }
            min.push(num);
        }
    }

    double GetMedian()
    {
        double res = 0.0;
        if(size == 0) return res;

        if(size & 1){
            res = max.top();
        }
        else{
            res = (max.top() + min.top()) / 2.0;
        }
        return res;
    }
};