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{N1}{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.javaC 版本见 lc_295_find_median_from_data_stream_s1.cpp。算法流程设元素总数为 $N m n$其中 $m$ 和 $n$ 分别为 $A$ 和 $B$ 中的元素个数。addNum(num)函数当 $m n$即 $N$ 为偶数需向 $A$ 添加一个元素。实现方法将新元素 $num$ 插入至 $B$再将 $B$ 堆顶元素插入至 $A$当 $m \ne n$即 $N$ 为奇数需向 $B$ 添加一个元素。实现方法将新元素 $num$ 插入至 $A$再将 $A$ 堆顶元素插入至 $B$。这里的关键在于假设插入数字 $num$ 遇到情况1.由于 $num$ 可能属于“较小的一半”即属于 $B$因此不能将 $num$ 直接插入至 $A$。而应先将 $num$ 插入至 $B$再将 $B$ 堆顶元素插入至 $A$。这样就可以始终保持 $A$ 保存较大一半、$B$ 保存较小一半即两个堆的“分界不变量”永远不会被破坏——这是一个“先借道过滤、再转交”的流程而不是简单的按值判断。findMedian()函数当 $m n$$N$ 为偶数则中位数为 $($ $A$ 的堆顶元素 $$ $B$ 的堆顶元素 $)/2$当 $m \ne n$$N$ 为奇数则中位数为 $A$ 的堆顶元素。约定 $A$ 在奇数长度时多存一个元素使得奇数场景下中位数恰好就是 $A$ 的堆顶查询只需 $O(1)$ 读堆顶无需任何额外计算。三种语言实现对照Pythonheapq小顶堆 取反实现大顶堆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可直接运行验证。JavaPriorityQueue自定义比较器Java 使用PriorityQueue((x, y) - (y - x))可方便实现大顶堆默认的PriorityQueue即小顶堆。class MedianFinder { QueueInteger 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; } }Cpriority_queue的greater与lessC 中greater为小顶堆less为大顶堆二者配合vectorint容器使用class MedianFinder { public: priority_queueint, vectorint, greaterint A; // 小顶堆保存较大的一半 priority_queueint, vectorint, lessint 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 仓库在多处收录了本题的完整可运行代码便于读者对照验证语言基础实现优化实现heappushpopPythonlc_295_find_median_from_data_stream_s1.pylc_295_find_median_from_data_stream_s2.pyJavalc_295_find_median_from_data_stream.java—Clc_295_find_median_from_data_stream_s1.cpp—此外剑指 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考