class Solution {
public:
    //动态维护两个堆，一个大根堆，一个小根堆，首先遇到元素无条件插入大根堆，如果大根堆
    //堆顶大于小根堆堆顶，交换两根堆堆顶元素，如果大根堆元素个数比小根堆元素多2，弹出
    //堆顶元素放到小根堆以维护两个堆的动态平衡，随后中位数就是大根堆和小根堆堆顶平均数
    //如果个数为奇数直接返回大根堆堆顶即可
    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()){
            int mine = min_heap.top(),maxe = max_heap.top();
            min_heap.pop(),max_heap.pop();
            max_heap.push(mine),min_heap.push(maxe);
        }
        if(max_heap.size() > min_heap.size() + 1){
            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.;
    }
};