本文共 1064 字，大约阅读时间需要 3 分钟。

如何得到一个数据流中的中位数

在处理数据流中的中位数问题时，可以通过维护两个堆来高效地实现。以下是详细的解决方案。

• 奇数个数据：排序后取中间的数值。
• 偶数个数据：排序后取中间两个数的平均值。

2. 高效算法方案一种常用的方法是使用两个堆来分别存储较小和较大的数，将它们保持在接近相等大小的状态。这种方法的时间复杂度为O(log n)，非常适合处理大规模数据流。

3. 数据结构选择

• 大根堆（max-heap）：存储较小的一部分数。
• 小根堆（min-heap）：存储较大的另一部分数。
4. 插入操作a. 插入新数值到大根堆。b. 比较大根堆和小根堆的顶元素，调整堆的顺序。c. 当大根堆比小根堆多两个元素时，取出大根堆的顶元素，插入到小根堆中。

5. 获取中位数

• 如果双方元素数量相等，返回两堆顶元素的平均值。
• 否则，直接返回大根堆的顶元素。

具体实现使用C++的优先队列<队列>模拟两堆结构。实现如下：

class Solution {public:priority_queue<int,vector

> maxh; // 大根堆priority_queue<int,vector
> minh; // 小根堆

void insert(int num) {    maxh.push(num);    if (!minh.empty() && maxh.top() > minh.top()) {        int x = maxh.top(), y = minh.top();        maxh.pop();        minh.pop();        maxh.push(y);        minh.push(x);    }    if (maxh.size() == minh.size() + 2) {        int x = maxh.top();        maxh.pop();        minh.push(x);    }}double getMedian() {    if (maxh.size() == minh.size())        return (maxh.top() + minh.top()) / 2.0;    return maxh.top();}

}

代码解释：

• 插入函数：将新数插入大根堆，然后调整堆的顺序以维持两个堆的关系。
• 取中位函数：判断两堆大小相同则返回平均值，否则返回大根堆顶元素。

通过这种方法，可以高效地处理数据流中的中位数问题。