1. 概述
本文将讲解如何实时计算一个整数数据流的中位数（Median）。
我们会先明确问题并给出示例，接着分析核心难点，最后通过 Java 实现几种高效的解决方案。重点是利用堆（Heap）结构优化性能，避免踩到 O(n) 插入时间的坑。
2. 问题描述
中位数是有序数据集中处于中间位置的值。对于一组整数：
- ✅ 奇数个元素：中位数就是正中间那个数。例如：
{5, 7, 10}的中位数是7 - ✅ 偶数个元素：中位数是中间两个数的平均值。例如：
{5, 7, 8, 10}的中位数是(7 + 8) / 2 = 7.5
现在，我们将问题从静态集合扩展到动态数据流。每读入一个新整数，都要能快速返回当前所有已读整数的中位数。
我们需要设计一个类，支持以下两个操作：
void add(int num); // 添加新整数
double getMedian(); // 获取当前中位数
举个例子：
add 5 // 集合 = {5}，中位数 = 5
get median -> 5
add 7 // 集合 = {5,7}，中位数 = (5+7)/2 = 6
get median -> 6
add 10 // 集合 = {5,7,10}，中位数 = 7
get median -> 7
add 8 // 集合 = {5,7,8,10}，中位数 = (7+8)/2 = 7.5
get median -> 7.5
虽然数据流理论上是无限的，但我们可以假设所有数据能放进内存。
3. 暴力解法（不推荐）
3.1. 使用有序列表
最直接的想法：用一个 List 存所有数，每次插入时保持有序，取中位数时直接按索引访问。
- ✅
getMedian()：O(1)，因为列表有序，直接取中间元素 - ❌
add(num)：O(n)，需要遍历找到插入位置并移动后续元素
虽然逻辑简单，但插入性能太差，数据量大时直接卡死，不适用于流式场景。
3.2. 优化思路：拆成两个有序列表
我们尝试优化插入性能。核心思想是：
把数据分成两半：
- 小的那一半用降序排列
- 大的那一半用升序排列
这样我们只需要维护两个列表的平衡，确保它们的大小差不超过 1。
插入逻辑如下：
if 新元素 < 大半部分的最小值:
插入小半部分（降序）
if 小半部分比大半部分多 2 个以上:
把小半部分的最大值移到大半部分开头（重新平衡）
else:
插入大半部分（升序）
if 大半部分比小半部分多 2 个以上:
把大半部分的最小值移到小半部分开头（重新平衡）
中位数计算：
if 两部分元素数量相等:
median = (小半部分最大值 + 大半部分最小值) / 2
else if 小半部分更多:
median = 小半部分最大值
else:
median = 大半部分最小值
⚠️ 虽然我们通过分治稍微优化了常数因子，但插入仍需遍历找位置，**时间复杂度还是 O(n)**，没本质提升。
关键洞察：我们频繁访问的是“最大值”和“最小值”，也就是每部分的第一个元素。如果能 O(1) 访问极值，并 O(log n) 插入，就好了。
4. 堆（Heap）解法
4.1. 堆的基本概念
堆是一种特殊的完全二叉树，通常用数组实现。Java 中用 PriorityQueue 表示。
堆的关键性质：
4.1.1. 最大堆（Max-Heap）
- 父节点 ≥ 子节点
- 根节点是最大值
4.1.2. 最小堆（Min-Heap）
- 父节点 ≤ 子节点
- 根节点是最小值
堆的核心操作时间复杂度：
| 操作 | 时间复杂度 |
|---|---|
find-min / find-max |
O(1) |
insert |
O(log n) |
delete-min / delete-max |
O(log n) |
这正是我们需要的：**极值访问 O(1)，插入 O(log n)**。
4.2. 解法一：双堆 + 显式比较
我们将“小半部分”和“大半部分”分别用堆来维护：
- ✅
maxHeap：存较小的一半，根是这部分的最大值 - ✅
minHeap：存较大的一半，根是这部分的最小值
插入时，先和 minHeap.peek() 比较，决定插哪边，然后检查是否失衡（大小差 > 1），失衡则从多的那边 poll() 一个给少的那边。
class MedianOfIntegerStream {
private Queue<Integer> minHeap, maxHeap;
MedianOfIntegerStream() {
minHeap = new PriorityQueue<>(); // 默认是最小堆
maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); // 反序 = 最大堆
}
void add(int num) {
if (!minHeap.isEmpty() && num < minHeap.peek()) {
maxHeap.offer(num);
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.offer(maxHeap.poll());
}
} else {
minHeap.offer(num);
if (minHeap.size() > maxHeap.size() + 1) {
maxHeap.offer(minHeap.poll());
}
}
}
double getMedian() {
if (minHeap.size() < maxHeap.size()) {
return maxHeap.peek();
} else if (minHeap.size() > maxHeap.size()) {
return minHeap.peek();
} else {
return (minHeap.peek() + maxHeap.peek()) / 2.0;
}
}
}
- ✅
getMedian()：O(1) - ✅
add()：O(log n)，最多 3 次堆操作
逻辑清晰，符合直觉，推荐作为首选方案。
4.3. 解法二：堆大小约束法（更巧妙）
这个解法更简洁，但理解起来稍绕。核心是维护一个不变式：
让
minHeap（大半部分）永远可以多一个元素，maxHeap（小半部分）严格保持为n/2。
即：
- 总数为偶数时：
minHeap.size() == maxHeap.size() - 总数为奇数时：
minHeap.size() == maxHeap.size() + 1
中位数总是 minHeap 的根（因为它多一个）。
插入策略简单粗暴：
void add(int num) {
if (两堆大小相等) {
// 此时要让 minHeap 多一个
maxHeap.offer(num);
minHeap.offer(maxHeap.poll()); // 先进 max，再把 max 的最大值“推”给 min
} else {
// minHeap 已经多一个，现在要恢复平衡
minHeap.offer(num);
maxHeap.offer(minHeap.poll()); // 先进 min，再把 min 的最小值“推”给 max
}
}
完整实现：
class MedianOfIntegerStream {
private Queue<Integer> minHeap, maxHeap;
MedianOfIntegerStream() {
minHeap = new PriorityQueue<>();
maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
}
void add(int num) {
if (minHeap.size() == maxHeap.size()) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
} else {
minHeap.offer(num);
maxHeap.offer(minHeap.poll());
}
}
double getMedian() {
if (minHeap.size() > maxHeap.size()) {
return minHeap.peek();
} else {
return (minHeap.peek() + maxHeap.peek()) / 2.0;
}
}
}
- ✅ 时间复杂度不变：
add仍是O(log n)，getMedian是O(1) - ✅ 代码更短，没有显式比较
- ⚠️ 缺点：逻辑不够直观，
add的正确性依赖“推”操作自动平衡，需要多想两步
5. 总结
| 方案 | 插入时间 | 查询时间 | 优点 | 缺点 |
|---|---|---|---|---|
| 有序列表 | O(n) |
O(1) |
简单 | 性能差 |
| 双堆 + 比较 | O(log n) |
O(1) |
逻辑清晰，易理解 | 略长 |
| 双堆 + 大小约束 | O(log n) |
O(1) |
代码简洁 | 不够直观 |
✅ 推荐使用“双堆 + 显式比较”方案，它平衡了性能与可维护性，是面试和生产中的稳妥选择。
堆在这里的妙处在于：我们并不需要整个数据有序，只需要快速拿到“中间区域”的极值。这种“只要头，不要全序”的思想，在很多流式处理场景中都非常实用。