朴素思路（最挫的）

1. 用一个vector保存数据流
2. 每次进行排序，然后返回中位数，此题也能AC

正统思路

维护2个堆，一个是大顶堆，一个是小顶堆，我们要维持2个原则：
1. 大顶堆的最大值要小于小顶堆的最小值
2. 大顶堆的元素个数n, 小顶堆的元素个数m，那么n - m < 2 也就是大顶堆元素个数要么等于小顶堆的元素个数，要么只能多一个，相等的情况，其实就是偶数个元素的情况，此时中位数就是2个堆得堆顶元素的平均值，个数多1的情况，就是奇数的情况，此时大顶堆的堆顶元素就是中位数.

class Solution {
public:
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    void insert(int num){
        max_heap.push(num);
        if (!min_heap.empty() && min_heap.top() < max_heap.top())
        {
            auto minval = min_heap.top(), maxval = max_heap.top();
            min_heap.pop(), max_heap.pop();
            min_heap.push(maxval), max_heap.push(minval);
        }
        while (max_heap.size() > min_heap.size() + 1)
        {
            auto x = max_heap.top();
            max_heap.pop();
            min_heap.push(x);
        }
    }

    double getMedian(){
        if (max_heap.size() + min_heap.size() & 1) return max_heap.top();
        else return (max_heap.top() + min_heap.top()) / 2.0;
    }
};

// 朴素做法
// class Solution {
// public:
//  vector<double> stream;
//     void insert(int num){
//         stream.push_back(num);
//         sort(stream.begin(), stream.end());
//     }
// 
//     double getMedian(){
//         int n = stream.size();
//         if (n % 2 == 0)  return (stream[n / 2] + stream[(n / 2) - 1]) / 2;
//         else return stream[n / 2];
//     }
// };