class Solution {
public:
    priority_queue<double, vector<double>, greater<int>>heap_min;
    priority_queue<double, vector<double>>heap_max;
    void insert(int num){
        heap_max.push(num);
        if (heap_min.size() && heap_min.top() < heap_max.top()) {
            double a = heap_min.top(), b = heap_max.top();
            heap_min.pop(), heap_max.pop();
            heap_min.push(b), heap_max.push(a);
        }
        if (heap_min.size() + 1 < heap_max.size()) {
            heap_min.push(heap_max.top());
            heap_max.pop();
        }
    }

    double getMedian(){
        if (heap_min.size() != heap_max.size()) return heap_max.top();
        return (heap_min.top() + heap_max.top()) / 2;
    }
};