题目描述

这题是大小堆的经典应用了，利用大小堆求解一个不断更新的数组的中位数。此时的做法就是利用大根堆存储前n/2到n/2+1个数字，小根堆存储剩下的数字，可以看出大根堆和小根堆的顶部就是我们需要的值。此时我们必须维护好两个堆中元素的个数关系，元素的大小关系，即大根堆的所有元素理应比小根堆的所有元素要小，如果违反了此规则，就需要进行元素的对换。

算法1

(暴力枚举) $O(n)$

C++ 代码

class Solution {
public:
    void insert(int num){
        maxHeap.push(num);
        if(maxHeap.size() > minHeap.size() + 1)
        {
            int t = maxHeap.top();
            maxHeap.pop();
            minHeap.push(t);
        }
        while(minHeap.size() && maxHeap.top() > minHeap.top())
        {
            int t1 = maxHeap.top();
            int t2 = minHeap.top();
            maxHeap.pop(); maxHeap.push(t2);
            minHeap.pop(); minHeap.push(t1);
        }
    }

    double getMedian(){
        int n1 = minHeap.size();
        int n2 = maxHeap.size();
        if(n1 == n2) return (minHeap.top() + maxHeap.top()) / 2.0;
        else return maxHeap.top();
    }
private:
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
};