题解34 | #升序小堆#降序大堆#数据流中的中位数#

#include <functional>
#include <queue>
class Solution {
private:
    priority_queue<int,vector<int>,less<int>> max; //大顶堆
    priority_queue<int,vector<int>,greater<int>> min; //小顶堆
    //此处容易出错，大顶堆是降序，应选less，小顶堆是升序，选greater
public:
    void Insert(int num) {
        if(max.empty() || num <= max.top()){//判断条件必须先判空
            max.push(num);
        }
        else {
            min.push(num);
        }

        int li = min.size();
        int la = max.size();
        //大堆里边多了的话
        if( la - li > 1){
            int top = max.top();
            min.push(top);
            max.pop();
        }
        //小堆里边多了的话
        else if(li - la > 1){
            int top = min.top();
            max.push(top);
            min.pop();
        }
       
    }

    double GetMedian() { 
        int li = min.size();
        int la = max.size();
        double mid;

        if(li > la){
            mid = min.top();
            return mid;
        }
        else if (la > li) {
            mid = max.top();
            return mid;
        }
        else {
            mid = double(max.top()+min.top())/2;
            return mid;
        }
    }

};

算法基本思想：

该算法使用两个堆来实现动态获取中位数的功能。

一个是大顶堆，存放较小的一半数；另一个是小顶堆，存放较大的一半数。

插入操作时，先将数插入到大顶堆中，再将大顶堆的堆顶元素插入到小顶堆中。保持两个堆的大小差不超过1。

1.获取中位数时，如果两个堆的大小相等，则取两个堆顶元素的平均值作为中位数；

2.如果大顶堆的大小比小顶堆大1，则中位数为大顶堆的堆顶元素；

3.如果小顶堆的大小比大顶堆大1，则中位数为小顶堆的堆顶元素。

时间复杂度：

插入操作的时间复杂度为O(log n)，获取中位数的时间复杂度为O(1)。

空间复杂度：

空间复杂度为O(n)，其中n为插入的元素个数。

头文件以及private部分的解释：

#include <functional>：引入了函数对象的头文件，用于定义堆的比较函数。

private部分：

priority_queue<int,vector<int>,less<int>> max;：定义了一个大顶堆，用于存放较小的一半数。

priority_queue<int,vector<int>,greater<int>> min;：定义了一个小顶堆，用于存放较大的一半数。