/*
将所有数据划分为两个集合：较大的一半归到小根堆，较小的一半归到大根堆
对新枚举到的元素，优先放入大根堆中，此时判断：
(1)若"大根堆.top() > 小根堆.top()"，则交换堆顶元素
(2)若"大根堆.size() > 小根堆.size() + 1"，则将大根堆的堆顶元素弹出至小根堆
------------------------
此时若总元素个数为奇数，则直接返回大根堆.top()；若总元素个数为偶数，则返回俩堆顶元素的平均值
*/

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.size() && max_heap.top() > min_heap.top()){   //情况(1)
            auto maxv = max_heap.top() , minv = min_heap.top();
            max_heap.pop(), min_heap.pop();
            max_heap.push(minv), min_heap.push(maxv);
        }
        if(max_heap.size() > min_heap.size() + 1){    //情况(2)
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }

    double getMedian(){
        if(max_heap.size() + min_heap.size() & 1){   //若总元素个数为奇数
            return max_heap.top();
        }else{
            return (max_heap.top() + min_heap.top()) / 2.0;
        }
    }
};