力扣295. 数据流的中位数

优先队列

• 思路：
  • 中位数是排序中间的数值：S1.M.S2
  • 可以使用两个优先队列来存放两边的数值，总是使得左侧的堆顶是最大的，右侧的堆顶是最小的，即使用大顶堆存放 S1，使用小顶堆存放S2，使得两个队列的 size 维持“平衡”，则中位数就会在两个堆顶“附近”了；
  • 维持两个队列 size 平衡：
    • 数据先 push 的大顶堆，如果是 > M 的数，则会在堆顶；如果是 < M 的数，则会沉入队列中；
    • 然后将堆顶的数 push 到小顶堆，如果是 > M 的数，会沉入队列；如果是 < M 的数，会在堆顶；
    • 将大顶堆的堆顶 pop；（因为已经 push 到小顶堆）
    • 判断一下两个队列的size，如果大顶堆的 size 少了，将小顶堆的堆顶“漏”到大顶堆；（可以将两个队列组合成漏斗，更直观）
  • 此时的中位数：
    • 如果大顶堆 size 多，则中位数是其堆顶；
    • 否则，为两个堆顶的均值；

class MedianFinder {
public:MedianFinder() {}void addNum(int num) {low.push(num);high.push(low.top());low.pop();if (low.size() < high.size()) {low.push(high.top());high.pop();}}double findMedian() {if (low.size() > high.size()) {return low.top();}return (low.top() + high.top()) / 2.0;}private:std::priority_queue<int, std::vector<int>, std::less<int>> low;std::priority_queue<int, std::vector<int>, std::greater<int>> high;
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/