题解 | 数据流中的中位数

#include <queue>
#include <functional>

using namespace std;

class Solution {
private:
    priority_queue<int> max_heap; // 大顶堆，存储较小的一半
    priority_queue<int, vector<int>, greater<int>> min_heap; // 小顶堆，存储较大的一半

public:
    void Insert(int num) {
        // 如果两个堆大小相等，优先插入大顶堆
        if (max_heap.size() == min_heap.size()) {
            // 如果要插入的数比小顶堆的最小值大，需要调整
            if (!min_heap.empty() && num > min_heap.top()) {
                min_heap.push(num);
                num = min_heap.top();
                min_heap.pop();
            }
            max_heap.push(num);
        } 
        // 如果大顶堆比小顶堆多一个元素，则插入小顶堆
        else {
            // 如果要插入的数比大顶堆的最大值小，需要调整
            if (!max_heap.empty() && num < max_heap.top()) {
                max_heap.push(num);
                num = max_heap.top();
                max_heap.pop();
            }
            min_heap.push(num);
        }
    }

    double GetMedian() { 
        if (max_heap.empty() && min_heap.empty()) {
            return 0.0;
        }
        
        if (max_heap.size() == min_heap.size()) {
            return (max_heap.top() + min_heap.top()) / 2.0;
        } else {
            return max_heap.top();
        }
    }
};

算法思路：
使用两个堆：
max_heap（大顶堆）：存储数据流中较小的一半数据
min_heap（小顶堆）：存储数据流中较大的一半数据

插入策略：
当两个堆大小相等时，新元素插入大顶堆
当大顶堆比小顶堆多一个元素时，新元素插入小顶堆
插入时可能需要调整，确保大顶堆的所有元素都小于等于小顶堆的所有元素

获取中位数：
如果两个堆大小相等，中位数是两个堆顶元素的平均值
如果大小不等（大顶堆多一个元素），中位数是大顶堆的堆顶元素
时间复杂度：
Insert操作：O(log n)，因为堆的插入操作是O(log n)
GetMedian操作：O(1)，只需访问堆顶元素

空间复杂度：
O(n)，用于存储数据流中的所有元素
这种方法确保了在任何时候都能快速获取中位数，同时插入操作也保持高效。