数据流中位数 (对顶堆)

引言：“中间人”问题

寻找已排序数组的中位数很简单 ($O(1)$)。但如果数据是一个流呢？

• 每次都排序： 每个新项进入都要耗费 $O(N \log N)$。太慢。
• 维护有序数组： 每次插入都需要 $O(N)$ 的位移操作。面对数百万个点依然太慢。

对顶堆 (Two Heaps) 模式允许你在 $O(1)$ 时间 内找到中位数，并在 $O(\log N)$ 时间 内添加新元素。它是实时统计监控的黄金标准。

算法要解决什么问题？

• 输入： 连续不断的数字流。
• 输出： 任意时刻的当前中位数。
• 承诺： 在插入和查询之间取得完美的性能平衡。

核心思想 (直觉版)

将数据分为两半：

1. 下半部分： 将较小的一半数据存储在 大顶堆 (Max-Heap) 中。这些小数字中最大的那个就在堆顶。
2. 上半部分： 将较大的一半数据存储在 小顶堆 (Min-Heap) 中。这些大数字中最小的那个就在堆顶。

中位数 永远要么是其中一个堆的堆顶（如果总数是奇数），或者是两个堆顶的平均值（如果总数是偶数）。

算法是如何工作的？

1. 平衡： 保持两个堆的大小几乎相等（差值 $\le 1$）。
2. 插入：
   • 将新数字添加到合适的堆中。
   • 如果堆变得不平衡，将较大堆的堆顶“移动”到较小的堆中。
3. 寻找中位数：
   • 如果总数是奇数，返回较大堆的堆顶。
   • 如果总数是偶数，返回 (大顶堆.top + 小顶堆.top) / 2。

典型业务场景

• ✅ 性能分析： 随着请求涌入，实时计算 Web 服务的“中值响应时间”。
• ✅ 金融科技： 在波动市场中实时计算资产的中值价格。
• ✅ 交互式数据应用： 在用户上传数据时，仪表盘实时更新统计指标。

性能与复杂度总结

• 添加元素： $O(\log N)$。
• 寻找中位数： $O(1)$。
• 空间： $O(N)$，需要存储所有项。

小结：一句话记住它

“对顶堆模式就像一把天平。通过将数据拆分为两个对立的堆，它让‘中间人’（中位数）始终坐在堆顶，让你能瞬间看到它。”