企业官网建设流程全解析

LeetCode-Book 题解精讲：数据流中的中位数（双堆法）——从 O(N) 有序插入到 O(log N) 堆平衡

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

本文基于 LeetCode-Book 仓库中《LCR 160. 数据流中的中位数》一文的解题框架展开，聚焦“动态数据流中如何高效维护中位数”这一经典高频面试题。文章以“有序数组 + 二分查找”的朴素思路为起点，推导出「小顶堆 + 大顶堆」双堆维护中位数的核心算法，并给出 Python / Java / C++ 三种语言的完整实现与优化细节。读完本文，你将掌握双堆法的插入流程、堆顶取中位数技巧、heappushpop组合操作的底层原理，并能直接在仓库对应源码与测试用例中验证运行效果。

问题背景与朴素思路

给定一长度为 $N$ 的无序数组，其中位数的计算方法为：首先对数组执行排序（使用 $O(N \log N)$ 时间），然后返回中间元素即可（使用 $O(1)$ 时间）。

但当数据以流的形式持续到达时，问题性质发生了变化：每次调用addNum(num)插入一个新元素后，都需要能立即回答“当前所有数据的中位数是多少”。如果每次都重新排序，代价不可接受。

针对本题，根据以上思路，可以将数据流保存在一个列表中，并在添加元素时保持数组有序。此方法的时间复杂度为 $O(N)$，其中包括：

• 查找元素插入位置 $O(\log N)$（二分查找）；
• 向数组某位置插入元素 $O(N)$（插入位置之后的元素都需要向后移动一位）。

数组在内存中是连续存储的，中间位置的插入天然伴随整体搬移，因此这种“有序插入”思路在插入操作上始终受制于 $O(N)$ 的移动成本。借助堆可进一步优化时间复杂度，将插入成本压缩到 $O(\log N)$，同时把中位数的查询成本降到 $O(1)$。

双堆法：用两个堆维护“较大一半”与“较小一半”

核心思想是：不维护完整有序数组，而是把数据流切分成两半，分别用两个堆来托管各自一半的最值。

建立一个小顶堆$A$ 和大顶堆$B$，各保存列表的一半元素，且规定：

• $A$ 保存较大的一半，长度为 $\frac{N}{2}$（$N$ 为偶数）或 $\frac{N+1}{2}$（$N$ 为奇数）；
• $B$ 保存较小的一半，长度为 $\frac{N}{2}$（$N$ 为偶数）或 $\frac{N-1}{2}$（$N$ 为奇数）。

这样的结构保证了两个堆之间天然存在一个“分界线”：

• 小顶堆 $A$ 的堆顶是“较大一半”中的最小值（即分界线上沿）；
• 大顶堆 $B$ 的堆顶是“较小一半”中的最大值（即分界线下沿）。

因此，中位数可仅根据 $A, B$ 的堆顶元素计算得到，无需遍历任何内部数据，两个堆顶就是离中位数最近的两个哨兵。

从仓库源码看，这一结构在三个代码库中均保持一致：selected_coding_interview/codes/python/lc_295_find_median_from_data_stream_s1.py与sword_for_offer/codes/python/sfo_41_find_median_from_data_stream_s1.py中的self.A（小顶堆）与self.B（大顶堆）注释完全一致；Java 版本见 lc_295_find_median_from_data_stream.java，C++ 版本见 lc_295_find_median_from_data_stream_s1.cpp。

算法流程

设元素总数为 $N = m + n$，其中 $m$ 和 $n$ 分别为 $A$ 和 $B$ 中的元素个数。

addNum(num)函数：

1. 当 $m = n$（即 $N$ 为偶数）：需向 $A$ 添加一个元素。实现方法：将新元素 $num$ 插入至 $B$，再将 $B$ 堆顶元素插入至 $A$；
2. 当 $m \ne n$（即 $N$ 为奇数）：需向 $B$ 添加一个元素。实现方法：将新元素 $num$ 插入至 $A$，再将 $A$ 堆顶元素插入至 $B$。

这里的关键在于：假设插入数字 $num$ 遇到情况1.，由于 $num$ 可能属于“较小的一半”（即属于 $B$），因此不能将 $num$ 直接插入至 $A$。而应先将 $num$ 插入至 $B$，再将 $B$ 堆顶元素插入至 $A$。这样就可以始终保持 $A$ 保存较大一半、$B$ 保存较小一半，即两个堆的“分界不变量”永远不会被破坏——这是一个“先借道过滤、再转交”的流程，而不是简单的按值判断。

findMedian()函数：

1. 当 $m = n$（$N$ 为偶数）：则中位数为 $($ $A$ 的堆顶元素 $+$ $B$ 的堆顶元素 $)/2$；
2. 当 $m \ne n$（$N$ 为奇数）：则中位数为 $A$ 的堆顶元素。

约定 $A$ 在奇数长度时多存一个元素，使得奇数场景下中位数恰好就是 $A$ 的堆顶，查询只需 $O(1)$ 读堆顶，无需任何额外计算。

三种语言实现对照

Python：heapq小顶堆 + 取反实现大顶堆

Python 中heapq模块是小顶堆。实现大顶堆的方法：小顶堆的插入和弹出操作均将元素取反即可——存入-num，取出时再取反还原。

from heapq import * class MedianFinder: def __init__(self): self.A = [] # 小顶堆，保存较大的一半 self.B = [] # 大顶堆，保存较小的一半 def addNum(self, num: int) -> None: if len(self.A) != len(self.B): heappush(self.A, num) heappush(self.B, -heappop(self.A)) else: heappush(self.B, -num) heappush(self.A, -heappop(self.B)) def findMedian(self) -> float: return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0

注意findMedian中偶数场景的写法是(self.A[0] - self.B[0]) / 2.0：因为 $B$ 中存储的是取反后的值，-self.B[0]才是真实的最大值，故self.A[0] - self.B[0]等价于A 堆顶 + B 真实堆顶。该实现与仓库 lc_295_find_median_from_data_stream_s1.py 完全一致，仓库中还内置了测试用例：依次addNum(1)、addNum(2)后中位数为 1.5，再addNum(3)后中位数为 2，可直接运行验证。

Java：PriorityQueue自定义比较器

Java 使用PriorityQueue<>((x, y) -> (y - x))可方便实现大顶堆，默认的PriorityQueue即小顶堆。

class MedianFinder { Queue<Integer> A, B; public MedianFinder() { A = new PriorityQueue<>(); // 小顶堆，保存较大的一半 B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半 } public void addNum(int num) { if(A.size() != B.size()) { A.add(num); B.add(A.poll()); } else { B.add(num); A.add(B.poll()); } } public double findMedian() { return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0; } }

C++：priority_queue的greater与less

C++ 中greater为小顶堆，less为大顶堆，二者配合vector<int>容器使用：

class MedianFinder { public: priority_queue<int, vector<int>, greater<int>> A; // 小顶堆，保存较大的一半 priority_queue<int, vector<int>, less<int>> B; // 大顶堆，保存较小的一半 MedianFinder() { } void addNum(int num) { if(A.size() != B.size()) { A.push(num); B.push(A.top()); A.pop(); } else { B.push(num); A.push(B.top()); B.pop(); } } double findMedian() { return A.size() != B.size() ? A.top() : (A.top() + B.top()) / 2.0; } };

三种语言的addNum流程完全同构：奇数分支“先入 A 再转交 A 顶给 B”，偶数分支“先入 B 再转交 B 顶给 A”，仅堆 API 与比较器写法不同，便于在面试中跨语言迁移。

进阶优化：heappushpop组合操作

Python 官方文档对heapq中组合操作有如下说明：

Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().

即heappushpop(heap, item)一次完成“先入堆、再弹出堆顶”，其内部实现比先heappush()再单独heappop()更高效（省去一次堆重构的部分开销）。根据以上文档说明，可将 Python 代码优化为：

from heapq import * class MedianFinder: def __init__(self): self.A = [] # 小顶堆，保存较大的一半 self.B = [] # 大顶堆，保存较小的一半 def addNum(self, num: int) -> None: if len(self.A) != len(self.B): heappush(self.B, -heappushpop(self.A, num)) else: heappush(self.A, -heappushpop(self.B, -num)) def findMedian(self) -> float: return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0

逐行解读优化版：

• 奇数分支（向 A 加元素）：heappushpop(self.A, num)先把num送入 $A$ 并弹出 $A$ 当前最小值（可能正是num本身），再-取反后压入 $B$，即“过滤后把较小的那一个转交给 B”；
• 偶数分支（向 B 加元素）：heappushpop(self.B, -num)先把-num送入 $B$ 并弹出 $B$ 的最小值（即原值最大者），再取反压入 $A$，完成“过滤后把较大的那一个转交给 A”。

优化版与基础版在结果上完全等价，但单次addNum由“两次 push + 一次 pop”变为“一次 pushpop + 一次 push”，堆操作的常数开销更低。仓库中的 lc_295_find_median_from_data_stream_s2.py 即为该优化版本的落地实现，其驱动代码同样以addNum(1) → addNum(2) → findMedian → addNum(3) → findMedian的顺序验证输出。

复杂度分析

• 时间复杂度：
  • 查找中位数 $O(1)$：获取堆顶元素使用 $O(1)$ 时间；
  • 添加数字 $O(\log N)$：堆的插入和弹出操作使用 $O(\log N)$ 时间。
• 空间复杂度 $O(N)$：其中 $N$ 为数据流中的元素数量，小顶堆 $A$ 和大顶堆 $B$ 最多同时保存 $N$ 个元素。

与朴素“有序数组”方案相比：查询中位数从“排序后取中间值”的 $O(N \log N)$ 或“有序插入”的 $O(N)$，分别降到 $O(1)$ 与 $O(\log N)$；代价是额外 $O(N)$ 空间存放两个堆，属于典型的“以空间换时间”的堆应用范式。

仓库中的可运行验证

LeetCode-Book 仓库在多处收录了本题的完整可运行代码，便于读者对照验证：

此外，剑指 Offer 题库中的对应题解 sfo_41_find_median_from_data_stream_s1.py 采用相同的双堆实现，其驱动代码将addNum与findMedian的返回值收集进列表后打印（[None, None, 1.5, None, 2]），是检验算法行为的又一可运行样例。Python 实现统一复用include包（见 include 目录），Java 与 C++ 分别依赖include.*与include/include.hpp，与本仓库其他题解保持一致的工程组织方式。

小结

数据流中位数问题是“堆”这一数据结构的代表性应用：通过小顶堆 $A$ 与大顶堆 $B$ 分别托管较大、较小两半数据，并利用堆顶哨兵以 $O(1)$ 查询中位数、$O(\log N)$ 插入新元素。本文给出的三种语言实现与heappushpop优化版本，在仓库中均有对应源码与测试驱动可直接运行验证，可作为面试复习与实战编码的速查参考。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book