class MedianFinder {
public:
    /** initialize your data structure here. */

    priority_queue<int>large;
    priority_queue<int, vector<int>, greater<int>>small;

    MedianFinder() {


    }

    void addNum(int num) {

        small.push(num);
        large.push(small.top());
        small.pop();

        if(small.size() < large.size()){
            small.push(large.top());
            large.pop();
        }

    }

    double findMedian() {

       if(small.size() > large.size())
           return small.top();
        else{
            return (small.top() + large.top())*1.0/2;
        }

    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */