堆的基本存储：用数组实现完全二叉树的原理与技巧

看到这个标题，你可能以为我要聊 JVM 调优，或者是一堆木块怎么码放。都不是。() 我要讲的是数据结构里的那个“堆”，而且只讲最底层的一件事：它到底是怎么被存进内存的。也就是“堆的基本存储”。网上搜索“堆”相关的内容，跳出来的热词相当混乱，有人卡在 IDEA 编译报java.lang.OutOfMemoryError，有人在问“堆和栈有什么差别”，还有人对着墙角的一堆小木块发愁。这些确实都和“堆”沾边，但它们是三件完全不同的事。

如果你正准备算法面试、正在学数据结构、或者想彻底搞清楚priority_queue和heapq背后发生了什么，这篇文章就是给你写的。我会把二叉堆的数组存储、父子下标换算、建堆和增删操作全部拆开揉碎，再结合我这些年实际写代码踩过的坑，让你看完之后能直接手写一个堆出来。

1. 先分清三个“堆”：数据结构堆、内存堆、墙角木块堆

在讲存储之前，我必须先把一件容易让人跑偏的事说清楚：程序员嘴里天天说的“堆”，至少有三种完全不同的含义。很多人学了很久还是犯迷糊，不是因为堆本身难，而是因为这个词重名重得太离谱。

1.1 数据结构里的堆：一种完全二叉树

数据结构里的“堆”，英文叫 Heap，指的是一棵完全二叉树，并且满足堆序性：对于小顶堆，任意父节点的值都小于等于它的两个孩子；大顶堆则相反，父节点大于等于孩子。注意，这里只看“父子关系”，兄弟之间谁大谁小无所谓。

我第一次理解这句话的时候，最大的感受是：堆的“有序”是一种很弱的有序。它不是像二分搜索树那样左小右大，而是只有垂直方向的约束。这就导致堆看起来有些“松”，但恰恰是这种松，让插入和删除可以在 O(log n) 时间内完成。

很多人看到“完全二叉树”这四个字就头疼。我用一个生活模型解释：你在一面墙角整齐地码正方体小木块，规则是每一层必须先码满，码满了才能往上一层继续堆，而且新堆的层必须从左往右连续摆放。这个形状，就是一棵完全二叉树。每一块木块看作一个节点，上层是父，下层是子。这也是为什么热词里出现“墙角堆放着一堆小木块”时，学算法的人会会心一笑——那确实是最直观的堆模型。

1.2 内存里的堆：和数据结构堆没有血缘关系

程序运行时，内存里有个区域也叫“堆”，英文同样叫 Heap。它由内存分配器管理，用来存放new、malloc出来的对象，和数据结构里的二叉堆没有任何血缘关系。热词里的“编译器的堆空间不足”“IDEA 编译时报java.lang.OutOfMemoryError: Java heap space”“进程堆大小调整为 8000 还是报错”，说的全是这块运行时内存。

我见过不少人学算法时看到“堆”，第一反应是去调 JVM 参数，这是典型的串台。后者的问题得从对象生命周期、内存泄漏、GC 参数、堆外缓存这些方向排查，和二叉堆里那个堆，除了发音一样，没有半点关系。我后面会专门用一个章节来说这个话题，因为它确实是高频困惑。

1.3 堆和栈：两组同名的概念一次说清

“堆和栈”也是热词，但这句话可能问的是两件完全独立的事。数据结构和数据结构之间，有栈（Stack）和堆（Heap）的区别；内存和内存之间，也有栈区（Call Stack）和堆区（Heap Segment）的区别。

算法里的栈是“后进先出”的线性结构，堆是“优先级最高先出”的树形结构，这是两种不同的逻辑结构。内存里的栈区存放局部变量和函数调用帧，堆区存放动态对象，这是两种不同的内存管理区域。热词里“win11 堆栈区溢出”，本质是函数调用栈爆了，通常要去查递归深度、局部大数组，跟堆区反而关系不大。

这四样东西名字两两相同，但彼此独立。你以后看到“堆”字，先停下来确认语境，再决定往哪个方向思考。

2. 堆的基本存储：用数组装下完全二叉树

现在进入正题。堆作为一种逻辑上的树结构，它在计算机里的物理存储方式，主流方案只有一个：顺序存储，也就是用一块连续的数组来装。这也是“堆的基本存储”这个标题真正想讲的东西。

2.1 为什么只有完全二叉树才能顺序存储

先给结论：完全二叉树特别适合顺序存储，普通二叉树不太适合。

顺序存储的意思很直白：把树从上到下、从左到右编号，按编号把节点值放进数组下标对应的位置。根节点放下标 0，第二层左边那个节点放下标 1，第二层右边放下标 2，以此类推。这样做的关键是，一棵完全二叉树不会在中间留下空洞，节点是紧凑排列的，数组大小正好等于节点数。

普通二叉树如果也用顺序存储，会出现大量的空位。比如根节点只有右孩子没有左孩子，按编号规则，左孩子的那个数组位置就空着。树越斜，浪费越严重。极端情况下，一棵只有 3 个节点的链式斜树，可能需要一个长度为 2 的幂次方的数组才能放下。所以普通二叉树通常用链式存储，也就是每个节点保存左右孩子指针。而堆因为保证“无空洞”，才能肆无忌惮地用数组裸存。

2.2 父子下标关系：左孩子 2i+1，右孩子 2i+2

数组存堆之后，最重要的就是下标换算。以 0 为起始下标为例，对于数组下标为i的节点：

• 左孩子下标：2 * i + 1
• 右孩子下标：2 * i + 2
• 父节点下标：(i - 1) / 2（整数除法）

这三条规则是整个堆实现的核心。所有上浮、下沉、建堆、排序，本质上都是在做下标移动。

我当初一直不理解为什么偏偏是这个公式。后来把下标写成二进制就通了：父节点下标i，左孩子下标是2i+1，右孩子是2i+2。二进制里，左孩子就是父节点下标左移一位再补个 1，右孩子是左移一位补个 0。因为完全二叉树按层编号的规律，从二进制上看天然就是这个结果。你不用记，画个三层满二叉树，把 0 到 6 标在节点旁边，自己走一遍就能推出来。建议你拿纸画一次，比背公式牢得多。

一个很容易被忽略的细节是：公式里的一个变体是左孩子2*i、右孩子2*i+1、父节点i/2，这是 1 起始下标的大小顶堆写法。两套体系都很常见，但它们混用会直接翻车。在文章第 5 章我会专门列出一张对照表，手写堆前最好先定死用哪一套。

2.3 一个堆对象该有的基本骨架

理解了批量下标规则，存一个堆就变成非常简单的事。定义一个数组，提供三个下标函数，再维护一个表示当前堆大小的变量。下面是最基本的小顶堆骨架：

#include <vector> #include <algorithm> using namespace std; class MinHeap { private: vector<int> h; int parent(int i) { return (i - 1) / 2; } int left(int i) { return 2 * i + 1; } int right(int i) { return 2 * i + 2; } public: bool empty() const { return h.empty(); } int size() const { return (int)h.size(); } int top() const { return h[0]; } };

注意这里我特意把vector当作连续存储的载体，它本质上就是一段可以动态增长的数组。堆的存储不需要指针，不需要next字段，所有关系都藏在数组下标里。听起来很神奇，但这就是顺序存储的威力：用位置表达关系，用一个数组表达整棵树。

Python 更直接，heapq模块底层就是一个普通list，你在list上调heapq.heapify，就把这个list变成了一个堆。所以理解堆的基本存储，等于理解了heapq的底层数据结构，也理解了 C++priority_queue的底层数据结构。

3. 建堆、入堆、出堆：把存储结构用起来

光有存储骨架不够，我们要在数组上做三种核心操作：建堆、插入元素、删除堆顶。这三个操作全部基于上一章节的下标换算。

3.1 向上调整建堆：从插入开始

先看最简单的方式：把数组当成空的，一个一个往里插。每次插入，新元素先放到数组末尾，也就是完全二叉树最后一个位置，然后和它的父节点比较。如果是小顶堆且新元素比父节点小，就交换，继续向上比较，直到不满足交换条件或者到达根节点。这个操作叫“上浮 shiftUp”，也叫“向上渗透”。

void push(int val) { h.push_back(val); int i = h.size() - 1; while (i > 0 && h[i] < h[parent(i)]) { swap(h[i], h[parent(i)]); i = parent(i); } }

插入为什么一定要放到末尾？因为堆必须是完全二叉树，数组末尾恰好对应完全二叉树的“最后一个位置”，直接放进去能保证树的形状不变。然后把值沿着父链向上蹿，直到它站到正确的位置。每次比较一路向上，最坏情况下要走树的高度，所以单次插入是 O(log n)。

用 n 个元素一个一个插入来建堆，总复杂度是 O(n log n)。这个复杂度不算差，但在算法竞赛和面试中，大家更愿意用下面这种能到达 O(n) 的建堆方式。

3.2 向下调整建堆：经典的 O(n) 建法

向下调整建堆叫 Floyd 建堆法，过程只有一句话：从倒数第一层最右边的非叶子节点开始，从右往左、从下往上，对每个节点执行一次“下沉”。

void heapify() { int n = h.size(); for (int i = n / 2 - 1; i >= 0; --i) siftDown(i); }

siftDown是把当前节点和两个孩子中更小的那个比较（小顶堆），如果当前节点大，就交换，然后继续顺着下沉方向往下处理，直到叶子或不再需要交换。

关键在于为什么从n / 2 - 1开始。编号大于等于n / 2的节点都是叶子，叶子没有孩子，不需要下沉。所以最后一个需要处理的非叶子节点，就是n / 2 - 1。从它开始逆着编号往前走，就能保证每次处理一个节点时，它的两个孩子已经各自是合法的堆。

这个建堆方式为什么是 O(n) 而不是看起来的 O(n log n)？因为绝大多数节点位于树的底层附近，深度小，下沉到底需要的比较次数也少。只有根附近少数节点需要走比较长的路。把所有节点的工作量加起来，结果是 O(n)。直观理解就是：木块金字塔里，底下那几层的木块数量最多，但它们只需要很少的局部整理；顶部那一个木块整理路径最长，但它只有一个。多数工作短，少数工作长，总量线性。

我建议初学的人别死记 O(n) 的数学证明，先亲手用[3, 1, 6, 5, 2, 4]跑一遍快速建堆和逐个插入建堆，对比两者经历过的交换次数，你会对“复杂度摊下来”这件事有更具体的感觉。

3.3 插入与删除堆顶：如何在数组中完整增删

删除堆顶是小顶堆里最核心的取最小值操作。套路：把数组第一个元素和最后一个元素交换，然后删掉最后一个元素，再对新的根节点执行下沉。

void pop() { if (h.empty()) return; h[0] = h.back(); h.pop_back(); siftDown(0); }

为什么删除堆顶要拿最后一个元素补到根上，而不是直接把孩子提上来？因为拿最后一个元素补位，才能保证完全二叉树的形状不变、数组没有洞。你如果贪图方便，把某个孩子直接提成根，树就可能出现中空，形状就破坏了，后续所有下标公式全部失效。

所以堆操作的通用口诀是：往结构尾部增，从结构尾部补。插入给尾部追加再上浮，删除用尾部覆盖根部再下沉。这个“尾部”意识是写堆最容易忽略但最重要的一条。

update（更新堆内某个值）这类操作，在这个数组存储体系里也顺理成章：更新数组对应位置后，判断新值相对旧值变大还是变小，选择执行上浮还是下沉。裸的二叉堆很难快速定位“某个值”的下标，所以实际工程里需要索引堆、配对堆或引入哈希表辅助。后面的优先级队列、Dijkstra 堆优化，都是在这个基础上扩展出来的。

3.4 一个可直接照抄的下沉模板

下沉容易写错，很多 bug 出在对“右孩子存在”和“比较对象”的处理上。我把常用的模板完整列出来：

void siftDown(int i) { int n = h.size(); while (true) { int l = left(i), r = right(i); int smallest = i; if (l < n && h[l] < h[smallest]) smallest = l; if (r < n && h[r] < h[smallest]) smallest = r; if (smallest == i) break; swap(h[i], h[smallest]); i = smallest; } }

这套写法的好处是：先假设当前节点是最小的，只有左右孩子合法才参与比较，循环里不需要额外判断叶子。很多教材用while (2*i+1 < n)之类的写法，也能用，但稍微改个下标基准就很容易弄混。我建议你固定用上面这种“候选最小”写法，换 0 基、1 基都只用改三个下标函数。

4. 从数组下标到实战算法：堆存储的真正价值

理解了“用数组装树”之后，你会发现很多进阶算法的地基其实是同一套东西。下面挑几个高频场景说，它们全部依赖顺序存储带来的“列位置即关系”特性。

4.1 堆排序：原地完成的省空间排序

堆排序就是最大程度利用了数组存储。思路非常干净：先把整个数组建成大顶堆，堆顶是最大值，把堆顶和数组末尾元素交换，然后把新的堆顶“下沉”到只剩前 n-1 个元素形成的堆中。重复这个交换-缩小-下沉的过程，数组尾部逐渐积累从大到小的有序序列。

这个排序的额外空间是 O(1)，排序过程完全不借助第二个数组。如果能利用数组原地完成，前提是什么？恰恰是堆本身存储在数组里，交换堆顶和末尾元素，本质上就是在同一个数组内部移动数据。如果当初用链式存储表示堆，堆排序就没这么优雅了。

堆排序不稳定、最佳最坏平均都是 O(n log n)。它适合大文件外排序、需要严格 O(1) 辅助空间的场合。实际业务里，std::sort、Arrays.sort通常用快速排序或归并排序，堆排序更多出现在“你必须手写”的考试题里，但它让你对“存储”的意义理解得更深。

4.2 流式数据中的 Top K 问题

有一类非常经典的面试题：在数据流中找第 K 大元素，或给海量数据求前 K 个最小值。这类问题最标准的解法就是堆，而且堆的存储优势在这里体现得淋漓尽致。

求前 K 小的大元素，就维护一个大小为 K 的小顶堆。每来一个新数，和堆顶（当前堆里的最大值）比较，比堆顶小就替换堆顶并下沉。整个过程只保留 K 个数，内存占用是 O(K)，但处理每个数是 O(log K)。

顺带提醒一个常见误区：热词里的“在一堆数据里凑出一个数”，这个描述很容易让人条件反射地掏出堆。但如果你真的遇到“从数组里找两个数，如果相加等于目标值”这样的题，那应该用哈希表，不是堆。堆擅长的是“动态维护极值、去除极值、找第 K 大”，它不擅长“精确匹配一个目标值”。看到“堆”字就上堆，是新手最容易犯的毛病。先判断问题形态，再决定数据结构。

4.3 由数组长度反推堆高与木块层数

回到墙角的小木块模型。给定一个堆数组的长度 n，我们能立刻反推出这棵完全二叉树有几层。如果从第 0 层算起，高度 h 满足：2^h <= n < 2^(h+1)，也就是说，一共堆了几层木块可以直接对 n 取以 2 为底的对数。

根据下标也能推层数：0 基下标 i 对应的节点在第floor(log2(i+1))层；1 基下标 i 对应第floor(log2(i)) + 1层。这个计算在画图调试时特别有用。比如你打印一个堆数组，想知道某个下标对应的节点在哪一层，用它就能快速定位，不用一个个在纸上画。

import math def level_in_heap(index_0based): return int(math.log2(index_0based + 1))

如果你恰恰在做“数数小木块”题目，记住完全二叉树的层数和节点总数之间的关系：第 k 层最多有2^k个节点，前 h 层满的时候总数是2^(h+1) - 1。这不只是一个几何题结论，它正是堆的数组长度和高度关系的数学本质。

5. 手写堆时的高频问题与排查心得

我这些年帮人 review 过不少手写堆，也自己在算法题里反复踩坑。下面的问题，几乎每个写堆的人都遇到过。

5.1 0 下标与 1 下标：哪套换算更顺手

两种下标方案：

0 基的优势是代码和vector、list天然对齐，建堆时非叶子起点是n/2 - 1；1 基的优势是位运算写起来好看，i>>1、i<<1，在执行效率和心理上都更顺，但数组第一个位置a[0]通常空着或放哨兵，浪费一个元素。

面试时我建议你直接用 0 基，理由是和语言内置容器一致，别人读你的代码不用额外反应。算法竞赛里一些人喜欢 1 基，那是为了把下标和题里从 1 开始的物理位置对齐。选一套就用到底，千万别写着写着混合起来。我自己见过太多次left(i) = 2 * i出现在 0 基代码里的惨案。

5.2 手写堆容易踩的 5 个坑

第一，忘记处理根节点。上浮循环条件必须同时写i > 0和比较条件，否则parent(0)在 0 基下等于(-1)/2，在 C++ 里是 0，程序可能死循环。第二，下沉时漏判右孩子。叶子判断不只靠“有没有左孩子”，还要检查右孩子是否越界。第三，建堆循环方向写反。很多人从 0 到 n-1 正向下沉，结果每个节点下沉时它的孩子还没形成合法堆，建完的数组根本不是堆。第四，删除堆顶后忘记pop_back()，导致“堆的大小”和“数组长度”对不上。第五，top()之前不判空。空堆取顶是未定义行为，在部分容器里直接崩溃。

5.3 内置优先队列与手写堆怎么选

C++ 的std::priority_queue默认是大顶堆，Python 的heapq默认是小顶堆。很多人刚开始会用错，其实就是没搞清“默认比较方向”。C++ 想用大顶堆直接传less<int>，想用小顶堆传greater<int>；Python 想求最大，就存相反数。

日常开发里能用内置就用内置，不要重复造轮子。但有两个场景我会手写堆：一是需要修改堆内某个元素且要求 O(log n)，内置优先队列做不到；二是需要在算法题里做“索引堆”“懒删除”这类定制操作时，内置接口反而别扭。手写堆的模板建议你背熟，不是为了炫技，而是面试官大概率会让你在白板上写。

5.4 别再让“堆空间不足”背黑锅

回到热词，IDEA 编译时报 java.lang.OutOfMemoryError: Java heap space、编译器堆空间不足、进程堆大小调整为 8000 还是报错，这些问题听起来带“堆”字，但排查方向完全不是数据结构这一套。

把-Xmx调到 8000m 仍然报错，说明要么编译期间需要的总内存已经超过你设置的数值，要么存在重复申请对象、内存没有及时释放、或者是元空间Metaspace、线程栈、直接内存等其他区域出问题。还有人提到的“堆外内存”，英文 Off-Heap Memory，指的就是 JVM 管理内存堆之外由进程直接分配的内存，一听名字容易联想到数据结构的堆，实际是内存管理领域的事。

我的建议是：以后在技术交流里提到“堆”，先明确一句你说的是“算法堆”还是“内存堆”。这个习惯能帮你省掉大量的沟通成本，也能避免把调优思路和算法思路搅在一起。

6. 可视化练习：画图比看代码管用

说了这么多，最有效的学习方式还是亲手画图。我建议你按下面这个顺序练一次，总计不超过 20 分钟，但对堆的理解会有质变。

第一步，在白纸上画一棵三层满二叉树，从上到下、从左到右在节点旁标 0 到 6。第二步，把[2, 4, 6, 8, 10, 12]填进去，此时它不一定满足堆序性。第三步，从下标 2 开始执行下沉，观察交换的路径；再对下标 1 执行下沉；最后对根执行下沉。每一步都用数组和树对照着看。第四步，手动把1插入这个堆，模拟 push 过程，跟踪它一路上浮到了哪里。

画完这四步，堆的基本存储就不会再有任何模糊地带。

6.1 可用来检验掌握程度的练习题

如果你想让这块知识真正长在自己身上，我建议按顺序做这几个经典题目：手写小顶堆的 push、pop、heapify；手写堆排序并在数组上原地完成；用大小为 K 的堆求一组数的 Top K；用两个堆维护数据流中位数；合并 K 个有序链表。

每做一题，都问自己三个问题：这次用的是 0 基还是 1 基？上升还是下沉？堆顶是最大值还是最小值？这三个问题能覆盖掉绝大多数堆相关代码的 bug 来源。练完你再看priority_queue文档、heapq源码，会突然觉得它们无比透明。

6.2 最后再分享一个我自己的核对技巧

每次写完堆，我从来不在大数据上直接验证，而是用一个只有四五个元素的数组，比如[1, 5, 3, 6, 2]，把上浮、下沉的所有分支都手动走一遍。走完再跑随机数据和内置优先队列做对拍。这个习惯帮我拦下了无数个“看起来没啥问题但就是不对”的下标错误。

还有一个小细节：C++ 里如果vector提前reserve足够容量，插入过程就不需要反复扩容，堆性能会明显好。虽然这是底层内存层面的优化，但它也提醒我们，堆的基本存储从来不只是“数组”两个字那么简单——你选择了连续存储，就应该尊重连续存储的脾气。理解了存储，才能理解性能，这才是“堆的基本存储”最核心的价值。