class Solution {
public:
    priority_queue<int> maxheap;
    priority_queue<int, vector<int>, greater<int>> minheap;

    void insert(int num){
        maxheap.push(num);//直接插入到下面的大根堆中
        //小根堆中有元素并且出现逆序，则需要交换
        while (minheap.size() && maxheap.top() > minheap.top()) {
            auto maxv = maxheap.top(), minv = minheap.top();//取出各自堆顶的值
            maxheap.pop(), minheap.pop();//弹出自个堆顶
            maxheap.push(minv), minheap.push(maxv);//插入堆顶从而完成交换
        }
        //下面的大根堆中的元素太多则需要分一些给小根堆,多两个
        if (maxheap.size() > minheap.size() + 1) {
            minheap.push(maxheap.top());
            maxheap.pop();
        }

    }

    double getMedian(){
        if (maxheap.size() + minheap.size() & 1) return maxheap.top();//如果是奇数个，那么中位数就是大根堆堆顶(整个序列的中间)
        return (maxheap.top() + minheap.top()) / 2.0;//因为是double类型，所以要除以2.0，不然就变成取整了
    }
};