class Solution {
public:
    priority_queue<int> maxheap;
    priority_queue<int,vector<int>,greater<int>> minheap;
    //思路，动态维护两个堆，拿到数时无条件往大根堆库插，如果大根堆堆顶大于小根堆堆顶，交换两个元素
    //如果大根堆元素个数大于小根堆元素加一，弹出大根堆中元素放到小根堆里，最后如果元素个数为奇数，
    //小根堆里弹出元素返回即可，偶数，取大小根堆堆顶除以2返回
    void insert(int num){
        maxheap.push(num);
        if(minheap.size() && maxheap.top() > minheap.top()){
            int maxe = maxheap.top(),mine = minheap.top();
            maxheap.pop(),minheap.pop();
            maxheap.push(mine),minheap.push(maxe);
        }
        if(maxheap.size() > minheap.size() + 1){
            minheap.push(maxheap.top());
            maxheap.pop();
        }
    }

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