class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int>maxHeap;
    priority_queue<int,vector<int>,greater<int>>minHeap;
    double med;
    MedianFinder() {
        med=0.0;
    }
    
    void addNum(int num) {
        if(maxHeap.size()==0){
            maxHeap.push(num);
        }
        else if(num>maxHeap.top()){
            minHeap.push(num);
        }
        else{
            maxHeap.push(num);
        }
        if(maxHeap.size()>minHeap.size()+1){
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
        else if(minHeap.size()>maxHeap.size()+1){
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        if(maxHeap.size()==minHeap.size()){
            med=(maxHeap.top()+minHeap.top())/2.0;
        }
        else if(maxHeap.size()>minHeap.size()){
            med=maxHeap.top();
        }
        else{
            med=minHeap.top();
        }
        return med;
    }
};