你问我为什么非要写一篇“堆的基本存储”这几年我在面试候选人和带新人做项目时反复撞见同一个现象很多人能随手默写堆排序的代码堆的插入删除也背得滚瓜烂熟但一问“为什么堆能用一块连续数组装下”“父节点下标为什么是(i-1)/2”“堆到底存在哪”就开始支支吾吾。说白了大家记住了套路却没有理解堆的“存储形态”。而这个存储形态恰恰决定了堆为什么能做到 O(log n) 级的插入删除、为什么能用于 Top K 问题、为什么在工程里会被各种奇技淫巧优化。这次我就把“堆的基本存储”彻底拆开讲透从堆的数据结构本质、数组映射关系、三大核心操作的存储维护到手写二叉堆、堆排序和 Top K 实战最后再整理一些我在真实工程里踩过的堆存储相关坑包括“堆已损坏”“编译器堆空间不足”这类听着吓人、其实有明确排查路径的问题。文章尽量语言无关但核心代码我用 Python 和 C 片段演示保证能直接抄走。顺带先消个疑“堆”这个词在中文技术圈里特别容易被认错。数据结构的堆、内存里的堆区、堆外内存、甚至某位讲 PyTorch 的博主“小土堆”、核工程里的“堆芯”完全是不同维度的东西。后文我会把这些概念逐个摘干净免得你在搜索时被带偏。1. 堆到底是什么它的存储方式为什么值得研究1.1 从优先队列说起如果你接触过操作系统调度、图算法里的 Dijkstra、或者数据库的归并排序大概率已经遇到过优先队列。优先队列的核心诉求很简单你要能快速拿到当前所有元素里最小或最大的那个同时还能快速往里塞新元素。如果用普通数组取最值只需遍历一次 O(n)但插入是 O(1)如果用有序链表插入要维护顺序是 O(n)取最值倒是 O(1)。无论怎么搭配总有一个操作要付出线性代价。堆就是专门解决这个矛盾的它在“保持部分有序”的前提下让插入和取最值都能做到 O(log n)。而它敢于这么做的底气就来自存储方式——一棵完全二叉树被紧凑地写进连续数组。可以说“堆的基本存储”就是堆所有优秀性质的地基。理解了存储你才真正理解了堆。1.2 堆是一种“弱序”的完全二叉树正式定义里堆这里主要指二叉堆是一棵完全二叉树同时满足堆序性质大根堆中任意节点的值不小于其子节点小根堆中任意节点的值不大于其子节点。注意这里说的是“不小于/不大于”它只约束父子关系不约束兄弟节点之间的顺序。也就是说堆是个“弱序”结构它比无序数组包含更多信息又比二叉搜索树少得多。这种“弱序”特征非常关键。正因为只需要维护父子之间的偏序关系堆才能在插入、删除时只沿着从叶到根或从根到叶的路径做交换路径长度就是树高也就是 O(log n)。而完全二叉树的形态紧凑树高严格控制在 log2(n) 级别不会像普通二叉树那样退化成链表。存储上完全二叉树天然适合用数组平铺不需要额外记录左右子节点指针这导致堆的空间开销非常小。1.3 先分清几个“堆”数据结构堆、运行时堆、堆外内存、小土堆在进入正题之前我先帮你把几个容易搜到但完全不同的概念摘干净。数据结构堆是本文主角它是一棵具备堆序性质的完全二叉树实际存储在数组里。运行时堆内存堆是另一个概念程序运行时的内存布局里通常会划分出栈区和堆区栈区由编译器自动管理函数调用时分配、返回时释放堆区则是程序员用 malloc、new 或者 GC 语言中的对象分配来申请的地方生命周期由人工或垃圾回收器控制。“堆已损坏”这类崩溃信息讲的就是运行时堆这个内存区域跟数据结构的堆一点关系都没有。堆外内存常见于 Java 等带 GC 的语言指在 JVM 管理的堆内存之外直接分配的内存典型用途是缓存大数据块或做网络通信的 DirectBuffer以减少 GC 压力。核工程里的“堆芯”更是完全不同的物理概念描述的是核反应堆的核心区域。至于“小土堆”那是一位很受欢迎的 PyTorch 教程 UP 主他的视频笔记跟数据结构堆毫无关系。我把这些列出来不是为了凑字数而是因为我在带人时确实发现很多人一旦被搜索热词干扰就会把原理搞混。2. 数组存储堆的核心逻辑下标就是指针2.1 完全二叉树与数组的天然映射堆用数组存储的原理可以归结为一句话完全二叉树按层序遍历的顺序可以无缝隙地铺进连续数组。从根节点开始每一层从左到右编号这棵树的节点编号就和数组下标一一对应。因为完全二叉树没有空洞所以不存在某个下标位置需要留空的情况空间利用率是 100%。这个映射带来的最大好处是不需要存任何指针。普通二叉树要用左右孩子指针把节点串起来每个节点至少消耗两个指针字段而在堆的数组实现里某节点该往左走还是往右走直接用下标算出来就行。你可以把这种下标换算理解成“用代数代替指针”这也是堆能在有限内存里装下大量元素的秘密武器。2.2 父子节点下标公式0基准和1基准假设数组从下标 0 开始大多数编程语言默认那么三条核心公式是下标i的左孩子2*i 1下标i的右孩子2*i 2下标i的父节点(i - 1) // 2如果数组从下标 1 开始很多教材为了简洁会这么写公式变成下标i的左孩子2*i下标i的右孩子2*i 1下标i的父节点i // 2为什么会有这两套公式核心原因是完全二叉树的层序编号具有一个性质第 k 层节点在数组中的连续区间正好等于前 k 层全部节点数的累计。于是任一节点的下一层子节点区间恰好从某个固定偏移开始推下来就得到这两组关系。0 基准的(i-1)//2本质上是2i1的反函数再向下取整。我强烈建议你亲手把i0到i6的父子关系用 Python 或者纸笔画一遍。画一棵高度 3 的完全二叉树再把它对应的数组写出来不用五分钟就能把公式刻进脑子里。2.3 为什么堆不用链式存储有人会问堆既然是一棵二叉树为什么不用带左右指针的节点来链式存储用二叉链表也能表达堆序性质插入删除照样 O(log n)但从工程角度看链式存储有致命缺点空间开销大。每个节点要额外存两个指针在 64 位系统里每个指针占 8 字节整棵堆的内存占用至少多出两倍。更重要的是链式节点的内存地址不连续CPU 缓存的局部性极差随机访问某个层级的节点时会频繁 miss。数组存储则在时间和空间上双赢分配一块连续内存读写相邻下标就是读写相邻地址缓存友好不需要指针省内存要随机访问第 k 层的节点直接按下标跳转是 O(1)。这也是堆排序能实现原地排序的重要原因——它可以在输入数组上直接调整成堆不额外借助树节点结构。链式堆在某些高级场景仍有存在感比如需要合并两个堆的左偏树、斜堆、斐波那契堆但作为基础二叉堆用数组存储是绝对主流。2.4 大根堆与小根堆的对称实现堆序性质有方向大根堆堆顶最大小根堆堆顶最小。实现上两者完全对称只需要把比较逻辑换一个方向。工程里要特别注意语言默认方向Python 的heapq默认是小根堆C 的std::priority_queue默认是大根堆Java 的PriorityQueue默认是小根堆。用错方向会导致取出来的顺序完全不对而且这种 bug 在数据量小时还不容易暴露。有个小技巧如果你手头只有小根堆的实现又想做大根堆可以把所有元素取负号再入堆取出时再取反。我在处理“最大的 K 个数”时经常这么干省得改比较器。这个技巧在 Python 里格外好用因为heapq不支持自定义比较函数要对类实例加__lt__才行取负是最省事的方案。3. 堆的三大基本操作插入、删除与建堆3.1 插入先放末尾再上浮向堆中插入元素的流程分两步先把新元素追加到数组末尾保持完全二叉树的形状然后从该位置开始“上浮”不断和父节点比较如果违反堆序小根堆里当前节点比父节点小就交换二者继续向上比较直到满足堆序或到达根节点。为什么必须先把元素放末尾因为堆首先必须是一棵完全二叉树完全二叉树的唯一插入位置就是“最后一个节点的下一个空位”也就是数组末尾。如果按“找空位插入”的思维放到中间完全二叉树的层序完整性就被破坏后续所有下标公式都会失效。这一点经常被忽略却是堆存储的根基。上浮操作的时间复杂度是 O(log n)最坏情况是从叶子一路换到根路径长度就是树高。不过在实际数据里上浮往往走不了几步因为新元素大概率不会是小根堆里的“最小值”平均插入成本比理论最坏情况低不少。3.2 删除堆顶末尾补位再下沉删除堆顶也就是取出最小值或最大值的流程同样分两步先用数组最后一个元素覆盖堆顶同时删除末尾然后从堆顶开始“下沉”在左右孩子中找出更小小根堆的那个如果当前节点比孩子大就交换继续向下直到满足堆序或到达叶子。这里有个值得强调的细节为什么用末尾元素补位而不是直接把某个孩子往上提因为末尾元素是最后一个叶子把它提到堆顶后整棵树的形状依然是完全二叉树只是堆序被破坏了。接下来通过一系列向下交换把堆序逐步恢复。整个过程同样只需要沿着一条从根到叶的路径走时间 O(log n)。如果直接把孩子往上提左右子树交接时很容易让形状脱离完全二叉树的范围后续维护变得非常麻烦。3.3 建堆自上而下插入 vs 自下而上下沉建堆有两种主流方式。第一种是“自上而下插入法”从空堆开始依次把每个元素 insert每次都做上浮。这种方式逻辑简单但总时间是 O(n log n)因为 n 个元素各做一次 O(log n) 的上浮。第二种更高效是“自下而上下沉法”也是堆排序最常用的建堆过程从最后一个非叶子节点开始逐个执行下沉操作。为什么从“最后一个非叶子节点”开始因为叶子节点本身没有孩子天然满足堆序不需要调整。最后一个非叶子节点的下标是n//2 - 10 基准从它往 0 反向遍历每个节点做一次下沉。自下而上建堆的时间复杂度是 O(n)而不是很多人直觉以为的 O(n log n)。原因在于越靠近根部的节点下沉路径越长但这样的节点数量很少越靠近叶子的节点下沉路径短但数量多。把每层的工作量累加起来是一个收敛的几何级数最终只有线性结果。这是堆存储分析里最容易被低估的结论也是一道常见面试题的来源。3.4 上浮和下沉的时间复杂度分析上浮和下沉的时间复杂度从数量级看都是 O(log n)但它们在实际运行中的常数因子不一样。上浮只需要比较当前节点和父节点单路比较交换路径单一下沉则需要在两个子节点里选出更小/更大的那个再比较多了一次分支判断和一次可能的孩子比较所以常数因子稍大。工程上的一个取舍是插入频繁、删除较少时优先保证上浮路径短删除频繁、堆顶吞吐量高时下沉的优化更关键。大多数标准库实现已经不在这两个操作上抠常数了而是在容量增长策略和比较器上做优化。你如果自己实现堆不必过度纠结上浮和下沉的常数差异把逻辑写对、边界处理好收益更大。4. 手写一个二叉堆完整代码与实战4.1 Python 实现小根堆下面是一个简短的 Python 小根堆实现我用它来演示数组存储的核心操作。代码刻意保持精简方便直接看逻辑。class MinHeap: def __init__(self): self._data [] def __len__(self): return len(self._data) def push(self, value): self._data.append(value) self._sift_up(len(self._data) - 1) def pop(self): if not self._data: raise IndexError(pop from empty heap) top self._data[0] last self._data.pop() if self._data: self._data[0] last self._sift_down(0) return top def peek(self): return self._data[0] def _sift_up(self, i): data self._data while i 0: parent (i - 1) // 2 if data[i] data[parent]: data[i], data[parent] data[parent], data[i] i parent else: break def _sift_down(self, i): data self._data n len(data) while True: left 2 * i 1 right 2 * i 2 smallest i if left n and data[left] data[smallest]: smallest left if right n and data[right] data[smallest]: smallest right if smallest ! i: data[i], data[smallest] data[smallest], data[i] i smallest else: break注意pop里有个细节堆顶被末尾元素覆盖后如果原堆只有一个元素那么pop()后数组会变成空此时不需要再执行下沉所以要先判断self._data是否非空。这个边界条件我见过不少人漏掉导致空堆继续下沉越界。另外_sift_down里left和right的下标检查不能省这是数组存储堆最常见的崩溃来源。4.2 用堆解决 Top K 问题堆最经典的应用之一是“找最大/最小的 K 个数”。以“海量数据里找最小的 K 个”为例正确姿势是维护一个大小为 K 的大根堆每当新来一个数如果堆没满就直接入堆如果堆已满且新数比堆顶小就用新数替换堆顶并下沉。这样堆里始终保留着当前见过的“最小的 K 个”。遍历完一遍数据堆内所有元素就是答案。为什么用大根堆而不是小根堆因为我们要“淘汰”当前 K 个里最大的那个也就是堆顶。如果用小根堆堆顶反而是当前最小的新来的大数无法判断该不该被淘汰逻辑会变得很别扭。用大根堆时新数只需要和堆顶比较一次如果比堆顶小就做一次 O(log K) 的下沉替换整体复杂度是 O(n log K)非常适合 K 远小于 n 的场景。我当时在实际项目里用这个思路处理过千万级日志里的异常关键词提取内存占用只有几十 KB速度比排序后取前 K 快了一个量级。如果你在面试里碰到 Top K 问题优先想堆不要一上来就排序。4.3 用堆做堆排序堆排序分两阶段建堆加反复取堆顶。原地堆排序的做法是先把整个数组调整成大根堆然后循环把堆顶最大值和当前末尾元素交换交换后堆大小减一再对新的堆顶做下沉。这样每一轮都“提取”出一个最大值放到末尾最终数组有序。这里有一个很容易搞混的点堆排序要用大根堆还是小根堆升序排序用大根堆降序排序用小根堆。因为每次取堆顶后我们要把它放到“当前数组末尾”末尾是升序序列的尾部所以堆顶必须留最大值。如果用小根堆做升序取到的是最小值放到末尾就反了。堆排序的时间复杂度稳定在 O(n log n)空间 O(1)但它是不稳定排序。不稳定性的来源是建堆和下沉过程中的长距离交换相同元素的相对顺序无法保证。需要稳定排序时应该选归并排序或者给元素加一个“原始序号”作为次级比较键。4.4 手写堆 vs 语言内置优先队列的取舍真实开发里我一般不推荐自己造堆除非你在学习阶段或者业务有特殊要求。Python 直接用heapqC 直接用std::priority_queueJava 用PriorityQueue这些实现久经考验性能稳定边界处理完善。手写堆最大的价值是帮你理解原理而不是在业务代码里炫技。什么时候需要手写最典型的是“需要删除任意元素”或“需要修改堆内某个元素的值”。标准库的优先队列通常只支持 push 和 pop没法 O(log n) 按键删除或更新。这时候你可以给堆加一个位置映射表比如用 dict 存“元素值 - 下标列表”在下沉、上浮时同步更新下标就能实现带更新的优先队列。我自己在写带权图最短路时经常用这个增强版堆效果很好。5. 堆存储在真实工程中的坑与排查实录5.1 下标越界最常见也最隐蔽手写堆最容易翻车的就是下标计算。你可能会在_sift_down里访问data[left]时忘记检查left n结果一旦当前节点的左孩子下标超出数组长度程序直接抛越界异常。别看这问题小它在递归式实现里特别隐蔽因为越界访问可能发生在深层递归中报错位置离真正的逻辑错误很远。我的排查方法永远是先把堆数组和索引位置打印出来把i, left, right, n四个值打出来看一眼。如果 left 或 right 已经大于等于 n说明已经到达叶子节点区间应该终止下沉。边界条件可以统一记成下沉的循环条件主体是left nright 再单独判断。这个习惯帮我避免了很多次深夜改 bug 的崩溃。5.2 堆已损坏C/C 工程中的内存堆踩坑热词里有“vs c 堆已损坏”这其实是在讲运行时内存堆的典型崩溃信息常见于 Visual Studio 的调试模式。中文环境里的一般报错是“检测到堆已损坏”或“HEAP CORRUPTION DETECTED”根本原因是程序越界写了堆区内存破坏了相邻堆块的管理信息。这种崩溃最讨厌的地方在于它往往不会在发生越界的瞬间报错而是在下一次 malloc/free 时才发现导致问题定位非常困难。遇到这种错误我建议按顺序做三件事打开 Application Verifier 或 gflags让调试器在内存越界发生的瞬间断下来。VS 自带的 CRT 调试堆通常会在 free 时发现损坏但发现问题时损坏已经发生你需要一个更早的断点。检查所有数组下标和 memcpy、strcpy 的字节数重点排查缓冲区溢出。一个经典案例给字符串分配了 n 字节却strcpy了一个 n1 字节的内容结尾的空字符写到了堆块外。检查 new/delete 或 malloc/free 是否配对释放后是否又通过悬挂指针写入了内存。这两个问题都会让堆管理元数据被破坏等下次分配或释放时才炸出来。5.3 编译器堆空间不足热词里的“编译器的堆空间不足”通常发生在编译大型模板项目或有着极深递归宏展开的代码时编译器自身用于语法分析、模板实例化的堆内存不够用了。遇到这种报错往往不是程序业务逻辑的问题而是编译环境资源的问题。我常用的处理手段先关闭并行编译比如 MSVC 的 /MP、GCC 的 -j减少多个翻译单元同时消耗编译资源然后检查是否存在模板递归过深或极大的结构体适当用类型别名拆分如果项目实在太大就升级构建机的内存或者拆分编译单元。实际项目中真正因为“编译器堆空间不足”崩溃的情况很少见常见于 Windows 上某些旧版 IDE 插件或 32 位编译进程地址空间受限时。遇到先看是不是 32 位进程内存吃紧再看是不是并行编译导致的内存峰值叠满。5.4 堆与栈的区别一张表讲清楚既然热词里反复出现“堆和栈的区别”我索性把最高频的对比整理成一张速查表方便你随时查阅对比维度栈堆管理方式编译器自动分配/释放程序员手动申请或由 GC 回收分配效率极快仅移动栈指针较慢需要查找空闲块容量较小默认 1MB~8MB较大可到数 GB生命周期函数返回即释放持续到手动释放或 GC典型报错栈溢出内存不足、堆损坏数据结构联系无直接关系无直接关系这里再次提醒数据结构堆、运行时栈、运行时堆名字有交叠但属于完全不同的知识体系。面试时如果被问“堆和栈的区别”大概率问的是运行时内存布局而不是数据结构堆你先搞清楚语境再回答。数据结构的堆是算法问题栈和堆的内存布局是操作系统问题两者不能混在一起讲。5.5 堆外内存Java 工程中的特殊存储场景热词里还有“堆外内存”这在 Java 后端调优中经常出现。JVM 的堆内内存受 GC 管理对象分配和回收都在这块区域内优点是开发省心缺点是 GC 停顿、大对象频繁晋升可能带来性能问题。堆外内存则绕开 JVM 堆直接通过操作系统分配一块内存典型实现有ByteBuffer.allocateDirect()和Unsafe.allocateMemory。堆外内存适合放生命周期很长、体量很大的数据比如网络收发缓冲区、缓存数据块因为不参与普通 GC可以显著降低 GC 压力。代价是分配和释放成本比堆内高而且需要小心回收常常依赖 Cleaner 机制或显式调用释放接口一旦泄漏很难排查。如果你的 Java 服务出现“Direct buffer memory”异常大概率是堆外内存用完了先检查是否有 ByteBuffer 没释放再考虑加大-XX:MaxDirectMemorySize。我在带实习生时经常说一句话堆排序的算法过程你背十遍不如把数组存储的下标推导一遍。我自己最早学堆是靠白纸手画完全二叉树、再按层序遍历填进数组画了大概二十棵树之后那些2i1、2i2的公式才算真正长在脑子里。这篇博文刻意把“存储”二字放在最前面就是因为建树、上浮、下沉、堆排序本质上全是存储结构在推动。最后再分享一个实用小技巧如果你在写代码时对某个堆操作的边界条件拿不准就先把堆数组打印出来加上断点用i走一遍上浮或下沉的完整路径比反复读代码快得多。堆的基本存储并不难难的是你愿不愿意先沉下心把那张数组和树的对应关系画出来。画明白了后面的路就顺了。
堆的基本存储：完全二叉树与数组的天然映射
你问我为什么非要写一篇“堆的基本存储”这几年我在面试候选人和带新人做项目时反复撞见同一个现象很多人能随手默写堆排序的代码堆的插入删除也背得滚瓜烂熟但一问“为什么堆能用一块连续数组装下”“父节点下标为什么是(i-1)/2”“堆到底存在哪”就开始支支吾吾。说白了大家记住了套路却没有理解堆的“存储形态”。而这个存储形态恰恰决定了堆为什么能做到 O(log n) 级的插入删除、为什么能用于 Top K 问题、为什么在工程里会被各种奇技淫巧优化。这次我就把“堆的基本存储”彻底拆开讲透从堆的数据结构本质、数组映射关系、三大核心操作的存储维护到手写二叉堆、堆排序和 Top K 实战最后再整理一些我在真实工程里踩过的堆存储相关坑包括“堆已损坏”“编译器堆空间不足”这类听着吓人、其实有明确排查路径的问题。文章尽量语言无关但核心代码我用 Python 和 C 片段演示保证能直接抄走。顺带先消个疑“堆”这个词在中文技术圈里特别容易被认错。数据结构的堆、内存里的堆区、堆外内存、甚至某位讲 PyTorch 的博主“小土堆”、核工程里的“堆芯”完全是不同维度的东西。后文我会把这些概念逐个摘干净免得你在搜索时被带偏。1. 堆到底是什么它的存储方式为什么值得研究1.1 从优先队列说起如果你接触过操作系统调度、图算法里的 Dijkstra、或者数据库的归并排序大概率已经遇到过优先队列。优先队列的核心诉求很简单你要能快速拿到当前所有元素里最小或最大的那个同时还能快速往里塞新元素。如果用普通数组取最值只需遍历一次 O(n)但插入是 O(1)如果用有序链表插入要维护顺序是 O(n)取最值倒是 O(1)。无论怎么搭配总有一个操作要付出线性代价。堆就是专门解决这个矛盾的它在“保持部分有序”的前提下让插入和取最值都能做到 O(log n)。而它敢于这么做的底气就来自存储方式——一棵完全二叉树被紧凑地写进连续数组。可以说“堆的基本存储”就是堆所有优秀性质的地基。理解了存储你才真正理解了堆。1.2 堆是一种“弱序”的完全二叉树正式定义里堆这里主要指二叉堆是一棵完全二叉树同时满足堆序性质大根堆中任意节点的值不小于其子节点小根堆中任意节点的值不大于其子节点。注意这里说的是“不小于/不大于”它只约束父子关系不约束兄弟节点之间的顺序。也就是说堆是个“弱序”结构它比无序数组包含更多信息又比二叉搜索树少得多。这种“弱序”特征非常关键。正因为只需要维护父子之间的偏序关系堆才能在插入、删除时只沿着从叶到根或从根到叶的路径做交换路径长度就是树高也就是 O(log n)。而完全二叉树的形态紧凑树高严格控制在 log2(n) 级别不会像普通二叉树那样退化成链表。存储上完全二叉树天然适合用数组平铺不需要额外记录左右子节点指针这导致堆的空间开销非常小。1.3 先分清几个“堆”数据结构堆、运行时堆、堆外内存、小土堆在进入正题之前我先帮你把几个容易搜到但完全不同的概念摘干净。数据结构堆是本文主角它是一棵具备堆序性质的完全二叉树实际存储在数组里。运行时堆内存堆是另一个概念程序运行时的内存布局里通常会划分出栈区和堆区栈区由编译器自动管理函数调用时分配、返回时释放堆区则是程序员用 malloc、new 或者 GC 语言中的对象分配来申请的地方生命周期由人工或垃圾回收器控制。“堆已损坏”这类崩溃信息讲的就是运行时堆这个内存区域跟数据结构的堆一点关系都没有。堆外内存常见于 Java 等带 GC 的语言指在 JVM 管理的堆内存之外直接分配的内存典型用途是缓存大数据块或做网络通信的 DirectBuffer以减少 GC 压力。核工程里的“堆芯”更是完全不同的物理概念描述的是核反应堆的核心区域。至于“小土堆”那是一位很受欢迎的 PyTorch 教程 UP 主他的视频笔记跟数据结构堆毫无关系。我把这些列出来不是为了凑字数而是因为我在带人时确实发现很多人一旦被搜索热词干扰就会把原理搞混。2. 数组存储堆的核心逻辑下标就是指针2.1 完全二叉树与数组的天然映射堆用数组存储的原理可以归结为一句话完全二叉树按层序遍历的顺序可以无缝隙地铺进连续数组。从根节点开始每一层从左到右编号这棵树的节点编号就和数组下标一一对应。因为完全二叉树没有空洞所以不存在某个下标位置需要留空的情况空间利用率是 100%。这个映射带来的最大好处是不需要存任何指针。普通二叉树要用左右孩子指针把节点串起来每个节点至少消耗两个指针字段而在堆的数组实现里某节点该往左走还是往右走直接用下标算出来就行。你可以把这种下标换算理解成“用代数代替指针”这也是堆能在有限内存里装下大量元素的秘密武器。2.2 父子节点下标公式0基准和1基准假设数组从下标 0 开始大多数编程语言默认那么三条核心公式是下标i的左孩子2*i 1下标i的右孩子2*i 2下标i的父节点(i - 1) // 2如果数组从下标 1 开始很多教材为了简洁会这么写公式变成下标i的左孩子2*i下标i的右孩子2*i 1下标i的父节点i // 2为什么会有这两套公式核心原因是完全二叉树的层序编号具有一个性质第 k 层节点在数组中的连续区间正好等于前 k 层全部节点数的累计。于是任一节点的下一层子节点区间恰好从某个固定偏移开始推下来就得到这两组关系。0 基准的(i-1)//2本质上是2i1的反函数再向下取整。我强烈建议你亲手把i0到i6的父子关系用 Python 或者纸笔画一遍。画一棵高度 3 的完全二叉树再把它对应的数组写出来不用五分钟就能把公式刻进脑子里。2.3 为什么堆不用链式存储有人会问堆既然是一棵二叉树为什么不用带左右指针的节点来链式存储用二叉链表也能表达堆序性质插入删除照样 O(log n)但从工程角度看链式存储有致命缺点空间开销大。每个节点要额外存两个指针在 64 位系统里每个指针占 8 字节整棵堆的内存占用至少多出两倍。更重要的是链式节点的内存地址不连续CPU 缓存的局部性极差随机访问某个层级的节点时会频繁 miss。数组存储则在时间和空间上双赢分配一块连续内存读写相邻下标就是读写相邻地址缓存友好不需要指针省内存要随机访问第 k 层的节点直接按下标跳转是 O(1)。这也是堆排序能实现原地排序的重要原因——它可以在输入数组上直接调整成堆不额外借助树节点结构。链式堆在某些高级场景仍有存在感比如需要合并两个堆的左偏树、斜堆、斐波那契堆但作为基础二叉堆用数组存储是绝对主流。2.4 大根堆与小根堆的对称实现堆序性质有方向大根堆堆顶最大小根堆堆顶最小。实现上两者完全对称只需要把比较逻辑换一个方向。工程里要特别注意语言默认方向Python 的heapq默认是小根堆C 的std::priority_queue默认是大根堆Java 的PriorityQueue默认是小根堆。用错方向会导致取出来的顺序完全不对而且这种 bug 在数据量小时还不容易暴露。有个小技巧如果你手头只有小根堆的实现又想做大根堆可以把所有元素取负号再入堆取出时再取反。我在处理“最大的 K 个数”时经常这么干省得改比较器。这个技巧在 Python 里格外好用因为heapq不支持自定义比较函数要对类实例加__lt__才行取负是最省事的方案。3. 堆的三大基本操作插入、删除与建堆3.1 插入先放末尾再上浮向堆中插入元素的流程分两步先把新元素追加到数组末尾保持完全二叉树的形状然后从该位置开始“上浮”不断和父节点比较如果违反堆序小根堆里当前节点比父节点小就交换二者继续向上比较直到满足堆序或到达根节点。为什么必须先把元素放末尾因为堆首先必须是一棵完全二叉树完全二叉树的唯一插入位置就是“最后一个节点的下一个空位”也就是数组末尾。如果按“找空位插入”的思维放到中间完全二叉树的层序完整性就被破坏后续所有下标公式都会失效。这一点经常被忽略却是堆存储的根基。上浮操作的时间复杂度是 O(log n)最坏情况是从叶子一路换到根路径长度就是树高。不过在实际数据里上浮往往走不了几步因为新元素大概率不会是小根堆里的“最小值”平均插入成本比理论最坏情况低不少。3.2 删除堆顶末尾补位再下沉删除堆顶也就是取出最小值或最大值的流程同样分两步先用数组最后一个元素覆盖堆顶同时删除末尾然后从堆顶开始“下沉”在左右孩子中找出更小小根堆的那个如果当前节点比孩子大就交换继续向下直到满足堆序或到达叶子。这里有个值得强调的细节为什么用末尾元素补位而不是直接把某个孩子往上提因为末尾元素是最后一个叶子把它提到堆顶后整棵树的形状依然是完全二叉树只是堆序被破坏了。接下来通过一系列向下交换把堆序逐步恢复。整个过程同样只需要沿着一条从根到叶的路径走时间 O(log n)。如果直接把孩子往上提左右子树交接时很容易让形状脱离完全二叉树的范围后续维护变得非常麻烦。3.3 建堆自上而下插入 vs 自下而上下沉建堆有两种主流方式。第一种是“自上而下插入法”从空堆开始依次把每个元素 insert每次都做上浮。这种方式逻辑简单但总时间是 O(n log n)因为 n 个元素各做一次 O(log n) 的上浮。第二种更高效是“自下而上下沉法”也是堆排序最常用的建堆过程从最后一个非叶子节点开始逐个执行下沉操作。为什么从“最后一个非叶子节点”开始因为叶子节点本身没有孩子天然满足堆序不需要调整。最后一个非叶子节点的下标是n//2 - 10 基准从它往 0 反向遍历每个节点做一次下沉。自下而上建堆的时间复杂度是 O(n)而不是很多人直觉以为的 O(n log n)。原因在于越靠近根部的节点下沉路径越长但这样的节点数量很少越靠近叶子的节点下沉路径短但数量多。把每层的工作量累加起来是一个收敛的几何级数最终只有线性结果。这是堆存储分析里最容易被低估的结论也是一道常见面试题的来源。3.4 上浮和下沉的时间复杂度分析上浮和下沉的时间复杂度从数量级看都是 O(log n)但它们在实际运行中的常数因子不一样。上浮只需要比较当前节点和父节点单路比较交换路径单一下沉则需要在两个子节点里选出更小/更大的那个再比较多了一次分支判断和一次可能的孩子比较所以常数因子稍大。工程上的一个取舍是插入频繁、删除较少时优先保证上浮路径短删除频繁、堆顶吞吐量高时下沉的优化更关键。大多数标准库实现已经不在这两个操作上抠常数了而是在容量增长策略和比较器上做优化。你如果自己实现堆不必过度纠结上浮和下沉的常数差异把逻辑写对、边界处理好收益更大。4. 手写一个二叉堆完整代码与实战4.1 Python 实现小根堆下面是一个简短的 Python 小根堆实现我用它来演示数组存储的核心操作。代码刻意保持精简方便直接看逻辑。class MinHeap: def __init__(self): self._data [] def __len__(self): return len(self._data) def push(self, value): self._data.append(value) self._sift_up(len(self._data) - 1) def pop(self): if not self._data: raise IndexError(pop from empty heap) top self._data[0] last self._data.pop() if self._data: self._data[0] last self._sift_down(0) return top def peek(self): return self._data[0] def _sift_up(self, i): data self._data while i 0: parent (i - 1) // 2 if data[i] data[parent]: data[i], data[parent] data[parent], data[i] i parent else: break def _sift_down(self, i): data self._data n len(data) while True: left 2 * i 1 right 2 * i 2 smallest i if left n and data[left] data[smallest]: smallest left if right n and data[right] data[smallest]: smallest right if smallest ! i: data[i], data[smallest] data[smallest], data[i] i smallest else: break注意pop里有个细节堆顶被末尾元素覆盖后如果原堆只有一个元素那么pop()后数组会变成空此时不需要再执行下沉所以要先判断self._data是否非空。这个边界条件我见过不少人漏掉导致空堆继续下沉越界。另外_sift_down里left和right的下标检查不能省这是数组存储堆最常见的崩溃来源。4.2 用堆解决 Top K 问题堆最经典的应用之一是“找最大/最小的 K 个数”。以“海量数据里找最小的 K 个”为例正确姿势是维护一个大小为 K 的大根堆每当新来一个数如果堆没满就直接入堆如果堆已满且新数比堆顶小就用新数替换堆顶并下沉。这样堆里始终保留着当前见过的“最小的 K 个”。遍历完一遍数据堆内所有元素就是答案。为什么用大根堆而不是小根堆因为我们要“淘汰”当前 K 个里最大的那个也就是堆顶。如果用小根堆堆顶反而是当前最小的新来的大数无法判断该不该被淘汰逻辑会变得很别扭。用大根堆时新数只需要和堆顶比较一次如果比堆顶小就做一次 O(log K) 的下沉替换整体复杂度是 O(n log K)非常适合 K 远小于 n 的场景。我当时在实际项目里用这个思路处理过千万级日志里的异常关键词提取内存占用只有几十 KB速度比排序后取前 K 快了一个量级。如果你在面试里碰到 Top K 问题优先想堆不要一上来就排序。4.3 用堆做堆排序堆排序分两阶段建堆加反复取堆顶。原地堆排序的做法是先把整个数组调整成大根堆然后循环把堆顶最大值和当前末尾元素交换交换后堆大小减一再对新的堆顶做下沉。这样每一轮都“提取”出一个最大值放到末尾最终数组有序。这里有一个很容易搞混的点堆排序要用大根堆还是小根堆升序排序用大根堆降序排序用小根堆。因为每次取堆顶后我们要把它放到“当前数组末尾”末尾是升序序列的尾部所以堆顶必须留最大值。如果用小根堆做升序取到的是最小值放到末尾就反了。堆排序的时间复杂度稳定在 O(n log n)空间 O(1)但它是不稳定排序。不稳定性的来源是建堆和下沉过程中的长距离交换相同元素的相对顺序无法保证。需要稳定排序时应该选归并排序或者给元素加一个“原始序号”作为次级比较键。4.4 手写堆 vs 语言内置优先队列的取舍真实开发里我一般不推荐自己造堆除非你在学习阶段或者业务有特殊要求。Python 直接用heapqC 直接用std::priority_queueJava 用PriorityQueue这些实现久经考验性能稳定边界处理完善。手写堆最大的价值是帮你理解原理而不是在业务代码里炫技。什么时候需要手写最典型的是“需要删除任意元素”或“需要修改堆内某个元素的值”。标准库的优先队列通常只支持 push 和 pop没法 O(log n) 按键删除或更新。这时候你可以给堆加一个位置映射表比如用 dict 存“元素值 - 下标列表”在下沉、上浮时同步更新下标就能实现带更新的优先队列。我自己在写带权图最短路时经常用这个增强版堆效果很好。5. 堆存储在真实工程中的坑与排查实录5.1 下标越界最常见也最隐蔽手写堆最容易翻车的就是下标计算。你可能会在_sift_down里访问data[left]时忘记检查left n结果一旦当前节点的左孩子下标超出数组长度程序直接抛越界异常。别看这问题小它在递归式实现里特别隐蔽因为越界访问可能发生在深层递归中报错位置离真正的逻辑错误很远。我的排查方法永远是先把堆数组和索引位置打印出来把i, left, right, n四个值打出来看一眼。如果 left 或 right 已经大于等于 n说明已经到达叶子节点区间应该终止下沉。边界条件可以统一记成下沉的循环条件主体是left nright 再单独判断。这个习惯帮我避免了很多次深夜改 bug 的崩溃。5.2 堆已损坏C/C 工程中的内存堆踩坑热词里有“vs c 堆已损坏”这其实是在讲运行时内存堆的典型崩溃信息常见于 Visual Studio 的调试模式。中文环境里的一般报错是“检测到堆已损坏”或“HEAP CORRUPTION DETECTED”根本原因是程序越界写了堆区内存破坏了相邻堆块的管理信息。这种崩溃最讨厌的地方在于它往往不会在发生越界的瞬间报错而是在下一次 malloc/free 时才发现导致问题定位非常困难。遇到这种错误我建议按顺序做三件事打开 Application Verifier 或 gflags让调试器在内存越界发生的瞬间断下来。VS 自带的 CRT 调试堆通常会在 free 时发现损坏但发现问题时损坏已经发生你需要一个更早的断点。检查所有数组下标和 memcpy、strcpy 的字节数重点排查缓冲区溢出。一个经典案例给字符串分配了 n 字节却strcpy了一个 n1 字节的内容结尾的空字符写到了堆块外。检查 new/delete 或 malloc/free 是否配对释放后是否又通过悬挂指针写入了内存。这两个问题都会让堆管理元数据被破坏等下次分配或释放时才炸出来。5.3 编译器堆空间不足热词里的“编译器的堆空间不足”通常发生在编译大型模板项目或有着极深递归宏展开的代码时编译器自身用于语法分析、模板实例化的堆内存不够用了。遇到这种报错往往不是程序业务逻辑的问题而是编译环境资源的问题。我常用的处理手段先关闭并行编译比如 MSVC 的 /MP、GCC 的 -j减少多个翻译单元同时消耗编译资源然后检查是否存在模板递归过深或极大的结构体适当用类型别名拆分如果项目实在太大就升级构建机的内存或者拆分编译单元。实际项目中真正因为“编译器堆空间不足”崩溃的情况很少见常见于 Windows 上某些旧版 IDE 插件或 32 位编译进程地址空间受限时。遇到先看是不是 32 位进程内存吃紧再看是不是并行编译导致的内存峰值叠满。5.4 堆与栈的区别一张表讲清楚既然热词里反复出现“堆和栈的区别”我索性把最高频的对比整理成一张速查表方便你随时查阅对比维度栈堆管理方式编译器自动分配/释放程序员手动申请或由 GC 回收分配效率极快仅移动栈指针较慢需要查找空闲块容量较小默认 1MB~8MB较大可到数 GB生命周期函数返回即释放持续到手动释放或 GC典型报错栈溢出内存不足、堆损坏数据结构联系无直接关系无直接关系这里再次提醒数据结构堆、运行时栈、运行时堆名字有交叠但属于完全不同的知识体系。面试时如果被问“堆和栈的区别”大概率问的是运行时内存布局而不是数据结构堆你先搞清楚语境再回答。数据结构的堆是算法问题栈和堆的内存布局是操作系统问题两者不能混在一起讲。5.5 堆外内存Java 工程中的特殊存储场景热词里还有“堆外内存”这在 Java 后端调优中经常出现。JVM 的堆内内存受 GC 管理对象分配和回收都在这块区域内优点是开发省心缺点是 GC 停顿、大对象频繁晋升可能带来性能问题。堆外内存则绕开 JVM 堆直接通过操作系统分配一块内存典型实现有ByteBuffer.allocateDirect()和Unsafe.allocateMemory。堆外内存适合放生命周期很长、体量很大的数据比如网络收发缓冲区、缓存数据块因为不参与普通 GC可以显著降低 GC 压力。代价是分配和释放成本比堆内高而且需要小心回收常常依赖 Cleaner 机制或显式调用释放接口一旦泄漏很难排查。如果你的 Java 服务出现“Direct buffer memory”异常大概率是堆外内存用完了先检查是否有 ByteBuffer 没释放再考虑加大-XX:MaxDirectMemorySize。我在带实习生时经常说一句话堆排序的算法过程你背十遍不如把数组存储的下标推导一遍。我自己最早学堆是靠白纸手画完全二叉树、再按层序遍历填进数组画了大概二十棵树之后那些2i1、2i2的公式才算真正长在脑子里。这篇博文刻意把“存储”二字放在最前面就是因为建树、上浮、下沉、堆排序本质上全是存储结构在推动。最后再分享一个实用小技巧如果你在写代码时对某个堆操作的边界条件拿不准就先把堆数组打印出来加上断点用i走一遍上浮或下沉的完整路径比反复读代码快得多。堆的基本存储并不难难的是你愿不愿意先沉下心把那张数组和树的对应关系画出来。画明白了后面的路就顺了。
