堆的基本存储：完全二叉树与数组的天然映射

你问我为什么非要写一篇“堆的基本存储”？这几年我在面试候选人和带新人做项目时，反复撞见同一个现象：很多人能随手默写堆排序的代码，堆的插入删除也背得滚瓜烂熟，但一问“为什么堆能用一块连续数组装下”“父节点下标为什么是(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本质上是2i+1的反函数再向下取整。

我强烈建议你亲手把i=0到i=6的父子关系用 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 - 1（0 基准），从它往 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 直接用heapq，C++ 直接用std::priority_queue，Java 用PriorityQueue，这些实现久经考验，性能稳定，边界处理完善。手写堆最大的价值是帮你理解原理，而不是在业务代码里炫技。

什么时候需要手写？最典型的是“需要删除任意元素”或“需要修改堆内某个元素的值”。标准库的优先队列通常只支持 push 和 pop，没法 O(log n) 按键删除或更新。这时候你可以给堆加一个位置映射表（比如用 dict 存“元素值 -> 下标列表”），在下沉、上浮时同步更新下标，就能实现带更新的优先队列。我自己在写带权图最短路时经常用这个增强版堆，效果很好。

5. 堆存储在真实工程中的坑与排查实录

5.1 下标越界：最常见也最隐蔽

手写堆最容易翻车的就是下标计算。你可能会在_sift_down里访问data[left]时忘记检查left < n，结果一旦当前节点的左孩子下标超出数组长度，程序直接抛越界异常。别看这问题小，它在递归式实现里特别隐蔽，因为越界访问可能发生在深层递归中，报错位置离真正的逻辑错误很远。

我的排查方法永远是先把堆数组和索引位置打印出来，把i, left, right, n四个值打出来看一眼。如果 left 或 right 已经大于等于 n，说明已经到达叶子节点区间，应该终止下沉。边界条件可以统一记成：下沉的循环条件主体是left < n，right 再单独判断。这个习惯帮我避免了很多次深夜改 bug 的崩溃。

5.2 堆已损坏：C/C++ 工程中的内存堆踩坑

热词里有“vs c++ 堆已损坏”，这其实是在讲运行时内存堆的典型崩溃信息，常见于 Visual Studio 的调试模式。中文环境里的一般报错是“检测到堆已损坏”或“HEAP CORRUPTION DETECTED”，根本原因是程序越界写了堆区内存，破坏了相邻堆块的管理信息。这种崩溃最讨厌的地方在于，它往往不会在发生越界的瞬间报错，而是在下一次 malloc/free 时才发现，导致问题定位非常困难。

遇到这种错误，我建议按顺序做三件事：

1. 打开 Application Verifier 或 gflags，让调试器在内存越界发生的瞬间断下来。VS 自带的 CRT 调试堆通常会在 free 时发现损坏，但发现问题时损坏已经发生，你需要一个更早的断点。
2. 检查所有数组下标和 memcpy、strcpy 的字节数，重点排查缓冲区溢出。一个经典案例：给字符串分配了 n 字节，却strcpy了一个 n+1 字节的内容，结尾的空字符写到了堆块外。
3. 检查 new/delete 或 malloc/free 是否配对，释放后是否又通过悬挂指针写入了内存。这两个问题都会让堆管理元数据被破坏，等下次分配或释放时才炸出来。

5.3 编译器堆空间不足

热词里的“编译器的堆空间不足”通常发生在编译大型模板项目或有着极深递归宏展开的代码时，编译器自身用于语法分析、模板实例化的堆内存不够用了。遇到这种报错，往往不是程序业务逻辑的问题，而是编译环境资源的问题。

我常用的处理手段：先关闭并行编译（比如 MSVC 的 /MP、GCC 的 -j），减少多个翻译单元同时消耗编译资源；然后检查是否存在模板递归过深或极大的结构体，适当用类型别名拆分；如果项目实在太大，就升级构建机的内存或者拆分编译单元。实际项目中，真正因为“编译器堆空间不足”崩溃的情况很少见，常见于 Windows 上某些旧版 IDE 插件或 32 位编译进程地址空间受限时。遇到先看是不是 32 位进程内存吃紧，再看是不是并行编译导致的内存峰值叠满。

5.4 堆与栈的区别：一张表讲清楚

既然热词里反复出现“堆和栈的区别”，我索性把最高频的对比整理成一张速查表，方便你随时查阅：

这里再次提醒：数据结构堆、运行时栈、运行时堆，名字有交叠，但属于完全不同的知识体系。面试时如果被问“堆和栈的区别”，大概率问的是运行时内存布局，而不是数据结构堆，你先搞清楚语境再回答。数据结构的堆是算法问题，栈和堆的内存布局是操作系统问题，两者不能混在一起讲。

5.5 堆外内存：Java 工程中的特殊存储场景

热词里还有“堆外内存”，这在 Java 后端调优中经常出现。JVM 的堆内内存受 GC 管理，对象分配和回收都在这块区域内，优点是开发省心，缺点是 GC 停顿、大对象频繁晋升可能带来性能问题。堆外内存则绕开 JVM 堆，直接通过操作系统分配一块内存，典型实现有ByteBuffer.allocateDirect()和Unsafe.allocateMemory。

堆外内存适合放生命周期很长、体量很大的数据，比如网络收发缓冲区、缓存数据块，因为不参与普通 GC，可以显著降低 GC 压力。代价是分配和释放成本比堆内高，而且需要小心回收，常常依赖 Cleaner 机制或显式调用释放接口，一旦泄漏很难排查。如果你的 Java 服务出现“Direct buffer memory”异常，大概率是堆外内存用完了，先检查是否有 ByteBuffer 没释放，再考虑加大-XX:MaxDirectMemorySize。

我在带实习生时经常说一句话：堆排序的算法过程你背十遍，不如把数组存储的下标推导一遍。我自己最早学堆，是靠白纸手画完全二叉树、再按层序遍历填进数组，画了大概二十棵树之后，那些2i+1、2i+2的公式才算真正长在脑子里。这篇博文刻意把“存储”二字放在最前面，就是因为建树、上浮、下沉、堆排序，本质上全是存储结构在推动。

最后再分享一个实用小技巧：如果你在写代码时对某个堆操作的边界条件拿不准，就先把堆数组打印出来加上断点，用i走一遍上浮或下沉的完整路径，比反复读代码快得多。堆的基本存储并不难，难的是你愿不愿意先沉下心把那张数组和树的对应关系画出来。画明白了，后面的路就顺了。