Two heaps

MedianFinder.cpp

class MedianFinder {
private:
    priority_queue<int> lomax;
    priority_queue<int, vector<int>, greater<int>> himin;
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        lomax.push(num);
        
        himin.push(lomax.top());
        lomax.pop();
        if(lomax.size() < himin.size()){
            lomax.push(himin.top());
            himin.pop();
        }
    }
    
    double findMedian() {
        return lomax.size() > himin.size() ? lomax.top() : (lomax.top() + himin.top()) * 0.5;
    }
};