题解 | #数据流中的中位数#

基本思路：

• 中位数是数组最中间的一个或两个元素，所以考虑直接将数组分为两部分，左边部分取最大值，右边部分取最小值，这种要求可以用堆（优先队列）满足。
• 如果数组元素个数为奇数，只需要取一个数，所以事先约定左边部分的元素个数一定大于右边部分，这样在数组元素个数为奇数时一直取左边部分的最大值。

class Solution {
public:
    priority_queue<int, vector<int>, less<int>> smaller;
    priority_queue<int, vector<int>, greater<int>> bigger;
    void Insert(int num) {
        smaller.push(num);
        bigger.push(smaller.top());
        smaller.pop();
        if (smaller.size() < bigger.size()) {
            smaller.push(bigger.top());
            bigger.pop();
        }
    }

    double GetMedian() { 
        if (smaller.size() == bigger.size()) {
            return ((double)smaller.top() + bigger.top()) / 2;
        }
        return (double)smaller.top();
    }

};