面试题41：数据流中的中位数

以最大堆保存较小一半、最小堆保存较大一半，由插入前的奇偶性决定目标堆，并在O(log n)插入后O(1)读取中位数。

学习目标

  • 能用最大堆+最小堆在 O(log n) 插入、O(1) 读取数据流中位数
  • 能解释"插入前奇偶性决定目标堆"与两条堆不变量的作用
  • 能说明两个堆大小差不超过 1 的平衡约束

从“中间两项才重要”开始

先预测：数字5、2、3、4依次到来。每次都重新排序能得到中位数，但会重复处理已经排好的大量关系。真正需要长期维护的只有一条分界：较小一半的最大值，以及较大一半的最小值。

作者用两个vector配合标准堆算法实现“数据流中的中位数”。源码变量 max 是，保存较小一半；变量 min 是，保存较大一半。名称按堆顶性质而不是数值区间命名，读反这两个变量会把奇数中位数放错边。

双堆夹住中位数：下半最大堆 + 上半最小堆321下半最大堆 max存较小一半，根 max[0]=3 最大456上半最小堆 min存较大一半，根 min[0]=4 最小max[0] ≤ min[0]3 ≤ 4偶数个：中位数 = (max[0]+min[0])/2 = (3+4)/2 = 3.5奇数个：min 多一个，中位数 = min[0]两堆数量差不超过 1；插入由奇偶定目标堆，越界则经另一堆转移边界值。插入 O(log n)、查询 O(1)。
作者变量名按堆类型命名：min是上半最小堆，max是下半最大堆。

三条必须同时成立的

第一条是顺序边界：最大堆保存较小一半，根 max[0] 是；最小堆保存较大一半，根 min[0] 是。所有下半元素都不大于所有上半元素。

第二条是数量平衡：两个堆大小差不超过1。作者进一步固定方向，min的大小只能等于max，或比max多1。因此总数为奇数时，多出来的那项永远在min，中位数就是min根；总数为偶数时两堆等大，中位数是两个根的平均。

第三条是元素守恒：每个输入恰好留在一个堆中。跨堆调整只能移动边界元素，不能复制或丢失。三条合起来，两个堆根节点就夹住全体数据的中点。

作者这种与“让最大堆多一个”的常见写法都可以正确，但查询规则必须与配额方向一致。旧页采用另一方向，却声称是在还原作者，这是需要纠正的。

插入前为偶数：目标是最小堆

当当前总数为偶数，两堆等大。插入后总数变奇数，作者要求min多一个，所以新元素最终必须进入min。

若num不小于max根，它本来就属于上半区，直接push到min。若num小于max根，它属于下半区：先push进max，新的max根就是下半区最大边界；再pop这个根，把它作为num推入min。这样较小的新值留在max，原边界被提升到min。

这个“先进入正确数值半区，再把边界送往配额目标堆”的动作称为。一次转移同时恢复顺序和数量，不需要反复交换。

插入前为奇数：目标是最大堆

此时min比max多一个。插入后总数变偶数，两堆必须等大，所以新元素最终进入max。

若num不大于min根，它属于下半区，直接push到max。若num大于min根，它属于上半区：先push到min，再弹出min根送入max。较大的新值留在上半区，原上半最小值下降为新的下半最大值。

插入状态配额目标越界处理插入后
插入前总数为偶数新值最终进入min若小于max根，先入max再把max根移到minmin比max多1
插入前总数为奇数新值最终进入max若大于min根，先入min再把min根移到max两堆重新等大
值落在正确半区直接push_heap不需要跨堆转移边界与配额同时成立
值落在错误半区先放入其应属堆弹出该堆边界到目标堆一次转移完成修复
作者不是“先随便入堆再反复平衡”，而是由奇偶决定目标堆，必要时经另一堆转移边界值。
#include <algorithm>
#include <functional>
#include <vector>
 
template <typename T>
class DynamicArray {
public:
    void Insert(T num) {
        if (((min.size() + max.size()) & 1) == 0) {
            if (max.size() > 0 && num < max[0]) {
                max.push_back(num);
                std::push_heap(
                    max.begin(), max.end(),
                    std::less<T>());
 
                num = max[0];
                std::pop_heap(
                    max.begin(), max.end(),
                    std::less<T>());
                max.pop_back();
            }
 
            min.push_back(num);
            std::push_heap(
                min.begin(), min.end(),
                std::greater<T>());
        } else {
            if (min.size() > 0 && min[0] < num) {
                min.push_back(num);
                std::push_heap(
                    min.begin(), min.end(),
                    std::greater<T>());
 
                num = min[0];
                std::pop_heap(
                    min.begin(), min.end(),
                    std::greater<T>());
                min.pop_back();
            }
 
            max.push_back(num);
            std::push_heap(
                max.begin(), max.end(),
                std::less<T>());
        }
    }
 
    T GetMedian() {
        const int size =
            static_cast<int>(min.size() + max.size());
        if (size == 0) {
            throw std::exception(
                "No numbers are available");
        }
 
        if ((size & 1) == 1) {
            return min[0];
        }
        return (min[0] + max[0]) / 2;
    }
 
private:
    std::vector<T> min;
    std::vector<T> max;
};

上面忠实保留作者结构与分支。push_heap要求加入的新元素先放到vector尾部；pop_heap把根交换到尾部，再由 pop_back 真正删除。比较器 less 产生最大堆，greater 产生最小堆。

逐次回放作者序列

作者用 DynamicArray<double>，依次插入5、2、3、4、1、6、7、0、8。交互图按数值边界展示两半，不声称是vector内部唯一堆排列；堆只保证根和父子关系，兄弟顺序可以不同。

插入5后min为5，奇数中位数5。插入2后max根2、min根5，平均3.5。插入3时两堆原本等大，3直接进入min并成为根，中位数3。

插入4前总数为3，4大于min根3，于是4先进入min，再把根3转移到max，两个根是3与4，中位数3.5。插入1前两堆等大，1小于max根3，于是1先进入max，再把根3转移到min，中位数回到3。

余下6、7、0、8重复相同规则，中位数依次为3.5、4、3.5、4。这个过程说明堆内不必完整排序，每次只维护边界根。

插入与查询复杂度

每次插入最多向一个堆push，再从该堆pop并向另一堆push，常数次堆操作均为O(log n)，所以插入O(log n)。每个数字永久保存在一个堆中，空间O(n)。

查询只读一个或两个根，时间O(1)。这正是结构相对“查询时排序”的优势：维护成本分摊到每次写入，读取不再扫描历史数据。

若写入远多于查询，可以把所有值追加到数组，在查询时用选择算法；若每次写入后都要查询，双堆更稳定。算法选择取决于写查比例，不是见到中位数就固定用堆。

模板名不等于任意类型都正确

场景作者行为边界工程策略
空流查询抛std::exception标准库构造在不同编译器不兼容现代接口可返回optional
奇数个double返回min[0]上半最小堆固定多一个O(1)查询
偶数个double(min[0]+max[0])/2测试保留小数大整数需防加法溢出
模板实例为int整数除法截断类名虽泛型，结果语义不泛化单独定义中位数类型
并发插入/查询源码无同步vector堆会被并发写破坏外部锁或快照
作者以double完成官方测试；模板换成int或并发服务后，需要重新定义返回与同步契约。

作者官方实例是double，所以偶数中位数保留0.5。若实例化为int，(min[0] + max[0]) / 2 使用整数除法，5与2会得到3而不是3.5；若T是大整数，先相加还可能溢出。模板语法通过不代表统计语义自动泛化。

空流查询抛异常。作者源码的 std::exception("...") 构造依赖Visual C++实现，标准可移植C++中 std::exception 没有消息字符串构造；可用 std::logic_error，或返回optional。

现代接口可固定存储double并返回optional，或为整数输入以long double计算平均。priority_queue直接封装堆操作，减少比较器与push_heap调用配对错误。

#include <functional>
#include <optional>
#include <queue>
#include <vector>
 
class MedianStream {
public:
    void insert(long long value) {
        if (upper.empty() ||
            value >= upper.top()) {
            upper.push(value);
        } else {
            lower.push(value);
        }
 
        if (upper.size() < lower.size()) {
            upper.push(lower.top());
            lower.pop();
        } else if (
            upper.size() > lower.size() + 1) {
            lower.push(upper.top());
            upper.pop();
        }
    }
 
    std::optional<long double> median() const {
        if (upper.empty()) {
            return std::nullopt;
        }
        if (upper.size() != lower.size()) {
            return static_cast<long double>(
                upper.top());
        }
        return (
            static_cast<long double>(upper.top()) +
            static_cast<long double>(lower.top())
        ) / 2.0L;
    }
 
private:
    std::priority_queue<long long> lower;
    std::priority_queue<
        long long,
        std::vector<long long>,
        std::greater<long long>> upper;
};

这版仍让上半最小堆多一个，但采用“先按边界入堆，再按数量搬根”的等价写法。它可能比作者奇偶分支多一次尺寸判断，语义更直观；两者都要用不变量测试证明。

作者十个检查时点

源码先对空结构调用GetMedian，期望捕获exception。随后每插入一个数字就调用Test，以绝对误差小于0.0000001比较double结果：

  1. 空流查询抛异常。
  2. 插入5，中位数5。
  3. 再插入2，中位数3.5。
  4. 再插入3，中位数3。
  5. 再插入4，中位数3.5。
  6. 再插入1，中位数3。
  7. 再插入6，中位数3.5。
  8. 再插入7，中位数4。
  9. 再插入0，中位数3.5。
  10. 再插入8，中位数4。

源码中的显示名称Test5与Test6顺序交换：插入4调用 Test("Test6")，插入1调用 Test("Test5")。这只是标签问题，执行顺序与期望值如上；重构测试时应按插入步编号，避免日志误导。

官方序列覆盖新值落在两侧和多个奇偶切换，但没有重复值、负数、极值、整数模板、NaN、无穷大或并发访问。随机属性测试可在每次插入后复制前缀、排序并计算参考中位数，再比较双堆结果；同时检查两个堆大小和根边界。

#include <algorithm>
#include <cassert>
#include <vector>
 
long double referenceMedian(
    std::vector<long long> values) {
    std::sort(values.begin(), values.end());
    const std::size_t middle = values.size() / 2;
    if ((values.size() & 1U) == 1U) {
        return values[middle];
    }
    return (
        static_cast<long double>(values[middle - 1]) +
        static_cast<long double>(values[middle])
    ) / 2.0L;
}
 
void testMedianStream() {
    MedianStream stream;
    assert(!stream.median().has_value());
 
    std::vector<long long> prefix;
    for (long long value :
         {5LL,2LL,3LL,4LL,1LL,6LL,7LL,0LL,8LL}) {
        prefix.push_back(value);
        stream.insert(value);
        assert(stream.median().value() ==
               referenceMedian(prefix));
    }
}

对重复值可测2、2、2；对极值可测long long最大值和最小值，确认先转换long double再相加不会整数溢出。若输入允许NaN，普通大小比较不形成全序，必须在入口拒绝或定义NaN放置策略。

服务化与并发边界

作者类没有同步。插入会修改两个vector并执行多步转移，查询若并发读取，可能在“已从一堆弹出、尚未推入另一堆”的瞬间观察到不平衡，甚至与vector扩容形成数据竞争。最简单的工程方案是插入和查询共享同一互斥锁；读多写少时可在写锁内发布中位数快照，让查询只读原子快照。

分布式分片不能只把每个分片的中位数再求中位数，那会忽略分片大小和分布。精确全局中位数需要可合并的秩结构、完整数据或协调选择；双堆状态本身不能仅凭四个根无损合并。

删除旧数据形成滑动窗口时，priority_queue不支持删除任意过期项。可用双堆加延迟删除哈希表，或两个multiset维护边界；这已是另一问题，必须新增“过期元素何时真正清除”的不变量。

持久化时，若只保存两个根就无法恢复后续插入；要保存两个堆全部元素或重放事件日志。恢复后还要校验元素总数、数量差和根边界，防止损坏快照把错误中位数静默带入服务。

本章练习

练习

问题 1： 为什么最大堆保存较小一半、最小堆保存较大一半？

问题 2： 插入前元素个数为偶数时，新元素应进入哪个堆？

问题 3： 插入与查询的时间复杂度分别是多少？

本章回顾

  1. 最大堆max保存较小一半，根是偶数中位数左边界。
  2. 最小堆min保存较大一半，根是奇数中位数或偶数右边界。
  3. 作者固定min数量等于max或多1，两个堆大小差不超过1。
  4. 插入前总数为偶数时新值最终进min，奇数时最终进max。
  5. 新值越过边界时先入所属半区，再把根转移到目标堆。
  6. 插入O(log n)、查询O(1)、存储O(n)。
  7. 作者用double；int模板会截断偶数中位数，极值相加可能溢出。
  8. 官方十个检查点包含空流和九次连续插入，但缺少随机与并发验证。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

最大堆
堆顶为最大值的堆，保存数据流中较小的一半。
最小堆
堆顶为最小值的堆，保存数据流中较大的一半。
不变量
算法保持的性质：较小一半的最大 ≤ 较大一半的最小，且两堆大小差 ≤1。
复习本章（5 题）

讨论

评论区加载中…