经典双堆（题解看注释）

C++ 代码

class MedianFinder {
private:
    priority_queue<int, vector<int>, greater<int>> bigger;
    priority_queue<int> smaller;
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        smaller.push(num);
        if(smaller.size() - bigger.size() == 1 && !bigger.empty()) {
            if(smaller.top() > bigger.top()) {
                int a = smaller.top(); smaller.pop();
                int b = bigger.top(); bigger.pop();
                smaller.push(b); bigger.push(a);
            }
        } else if(smaller.size() - bigger.size() == 2) {
            bigger.push(smaller.top()); smaller.pop();
        }
    }

    double findMedian() {
        if(smaller.size() - bigger.size() == 1) return smaller.top();
        else return (smaller.top() + bigger.top()) / 2.0;
    }
};

// if we use a array
// the insert may be slow, the worst o(N)
// the find is o(logN)

// we know that when insert a value in an sorted sequence
// the left part and the right part will change at most 1 value
// the value may be changed because the inserted value
// or the left part may be changed because swim up to the right part

// so lets seperate 2 parts and give a way to find the changed value
// when smaller part's value need to swim up to the bigger part
// we should find the biggest value of the smaller part
// so we need a big top heap
// and in order to know whether the value is bigger than 
// the smallest value of the bigger part
// we need a small top heap for bigger part

// so here the strategy is 2 heaps
// whenever the insertion occurs, we insert the value to the smaller part first.
// if the smaller part's size bigger than bigger part over 1, 
// we need to compare the top of 2 part, and swap if necessary
// the median will be the  top of smaller part
// if the smaller part's size bigger than bigger part over 2,
// move the top of smaller part to bigger part
// the median will be the median of 2 top

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