295. 数据流的中位数

https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/

295. 数据流的中位数 - 力扣（LeetCode）

添加数据:
保持小根堆的元素比大根堆的元素多一个,即:小根堆.size() - 大根堆.size() <=1

1.先添加到大根堆,此时可能不满足维持条件
2.所以把大根堆的堆顶元素放到小根堆中,然后大根堆的堆顶元素pop掉
3.判断大根堆和小根堆的size 如果小根堆的元素比大根堆的元素多2 -> 则需要把小根堆的堆顶放到大根堆,然后把小根堆的堆顶元素pop掉

插入的时候:
1.直接插入到大根堆,然后把大根堆的堆顶元素放到小根堆中,大根堆弹出元素 (因为要满足:小根堆的元素个数-大根堆的元素个数 = 1)

2.比较maxq.size()和minq.size()的关系
如果不满足:maxq.size()+1<minq.size(),就需要把小根堆的堆顶放到大根堆,然后小根堆弹出元素 (因为要满足:小根堆的元素个数-大根堆的元素个数 = 1)

返回中位数:
记小根堆+大根堆的元素个数为n个
如果n为奇数:返回小根堆的堆顶
如果n为偶数:返回小根堆堆顶元素+大根堆堆顶元素/2.0

class MedianFinder {
public:
    /** initialize your data structure here. */

    //构造函数
    MedianFinder() {
    }
    priority_queue<int> maxq;//大根堆
    priority_queue<int,vector<int>,greater<int>> minq;//小根堆

    //保持小根堆的元素比大根堆的元素多一个,即:小根堆.size() - 大根堆.size() <=1
    //添加元素:
    /*
        1.先添加到大根堆,此时可能不满足维持条件
        2.所以把大根堆的堆顶元素放到小根堆中,然后大根堆的堆顶元素pop掉
        3.判断大根堆和小根堆的size 如果小根堆的元素比大根堆的元素多2 -> 则需要把小根堆的堆顶放到大根堆,然后把小根堆的堆顶元素pop掉
    */
    void addNum(int num) {
        //无脑插入大堆
        maxq.push(num);
        //插入之后可能会改变:小根堆.size() - 大根堆.size() <=1 这个条件
        //所以把大根堆的堆顶放到小根堆,然后大根堆弹出元素
        minq.push(maxq.top());
        maxq.pop();

        //如果小根堆元素比大根堆元素多两个 
        if(maxq.size() +1 < minq.size())
        {
            //把小根堆的堆顶放到大根堆
            maxq.push(minq.top());
            minq.pop();//小根堆弹出数据
        }
    }
    //查找:
    /*
        记小根堆+大根堆的元素个数为n个
        如果n为奇数:返回小根堆的堆顶
        如果n为偶数:返回小根堆堆顶元素+大根堆堆顶元素/2.0
    */
    double findMedian() {
        int size = minq.size()+maxq.size();
        //注意返回的是double类型的数据！！
        if(size & 1) //奇数
        {
            return (double)minq.top();//返回小根堆的堆顶数据
        }
        else
        {
            return (maxq.top()+minq.top())/2.0;//返回(大根堆堆顶+小根堆堆顶)/2.0
        }
    }
};

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