题解 | 数据流中的中位数

#include <queue>
class Solution {
public:
    void Insert(int num) {
        ++cnt;
        if(cnt&1){
            if(!big.empty()&&big.top()>num){
                    int temp = big.top();
                    big.pop();
                    big.push(num);
                    num = temp;
            }
            small.push(num);
        }
        else{
            if(!small.empty()&&small.top()<num){
                int temp = small.top();
                small.pop();
                small.push(num);
                num = temp;
            }
            big.push(num);
        }
    }

    double GetMedian() { 
        if(cnt&1){
            return (double) small.top();
        }
        else{
            return (double)((small.top()+big.top())/2.0);
        }
    }
    priority_queue<int, vector<int>, greater<int> > small;
    priority_queue<int> big;
    int cnt = 0;
};

谈到中位数，第一想法是排好序的，但是插入排序时间复杂度太高，不考虑。

那么有什么其他考量呢？能不能让查找的时候再处理，其他时候就插入就好（时间复杂度上）。

那么我们应该用什么数据结构来存储呢？很容易想到AVL，如果它平衡的话就会在中间。

但是AVL写起来显然是有点复杂的，而且它平衡也很花时间。

于是干脆就用两个部分来做，小的和大的，中间的就在中间。

这就需要知道小的最大和大的最小，并且能够很快调整自己的结构。

刚好stl里有优先队列，那么就写一个小根堆和一个大根堆，再讨论奇数和偶数情况。

我是优先放在小根堆里，如果你要先放大根堆差不多。

插入和删除的时间复杂度都是O(logn)，但是查找可以到O(1)，插入n次也在常数O(knlogn)，也就是O(nlogn)，符合题目要求，可以接受。