对顶堆

对于中位数来说，是在有序序列中间的数

我们要保证有序，还要迅速求出中位数，我们用两个堆，一个堆维护区间的前面一段，一个堆维护区间的后面一段，这样我们能迅速求出前面一段的最大值，和后面一段的最小值。

我们规定要么两个堆一样多，要么左边多一个

对于插入操作：

• 如果左边的堆为空，或者t <= maxheap.top()，就插入左边

• 并且当两个维护两个堆大小最大差1，否则将多的一边的堆顶匀给另外一个堆

• 对于t > maxheap.top()，插入右边的堆即可。

对于求中位数：

• 只需要分类讨论奇数和偶数的情况

时间复杂度：插入$O(logN)$，求中位数$O(1)$

AC代码

class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int,vector<int>,greater<int>> minheap;
    priority_queue<int,vector<int>> maxheap;

    MedianFinder() {

    }

    void addNum(int num) {
        if (maxheap.empty() || num <= maxheap.top()){
            maxheap.push(num);
            if (maxheap.size() - minheap.size() > 1){
                minheap.push(maxheap.top());
                maxheap.pop();
            }
        } else {
            minheap.push(num);
            if (maxheap.size() - minheap.size() > 1){
                maxheap.push(minheap.top());
                minheap.pop();
            }
        }
    }

    double findMedian() {
        if ((minheap.size() + maxheap.size()) & 1) return maxheap.top();
        return (minheap.top() + maxheap.top()) / 2.0;
    }
};

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