大根堆，小根堆

数据流小于大根堆根节点则插入大根堆，否则插入小根堆，这样大根堆维护小的那一半，小根堆维护大的那一半．

class Solution {
public:
    void Insert(int num)
    {
        if (bigRootQueue.empty() || num <= bigRootQueue.top()) {
            bigRootQueue.push(num);
        } else {
            littleRootQueue.push(num);
        }
        if (bigRootQueue.size() > littleRootQueue.size() + 1) {
            littleRootQueue.push(bigRootQueue.top());
            bigRootQueue.pop();
        }
        if (littleRootQueue.size() > bigRootQueue.size()) {
            bigRootQueue.push(littleRootQueue.top());
            littleRootQueue.pop();
        }
    }

    double GetMedian()
    {
        int len = littleRootQueue.size() + bigRootQueue.size();
        if (len % 2) {
            return (double)bigRootQueue.top();
        } else {
            return (double)(bigRootQueue.top() + littleRootQueue.top()) / 2;
        }
    }

private:
    priority_queue<int, vector<int>, greater<int>> littleRootQueue;
    priority_queue<int, vector<int>, less<int>> bigRootQueue;
};