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

看到这个标题你可能以为我要聊 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 堆栈区溢出”本质是函数调用栈爆了通常要去查递归深度、局部大数组跟堆区反而关系不大。概念类别特点数据结构堆二叉堆逻辑结构完全二叉树支持取最大/最小元素数据结构栈逻辑结构线性结构后进先出内存堆区内存管理区域动态分配手动或靠 GC 释放内存栈区内存管理区域函数调用帧自动分配释放这四样东西名字两两相同但彼此独立。你以后看到“堆”字先停下来确认语境再决定往哪个方向思考。2. 堆的基本存储用数组装下完全二叉树现在进入正题。堆作为一种逻辑上的树结构它在计算机里的物理存储方式主流方案只有一个顺序存储也就是用一块连续的数组来装。这也是“堆的基本存储”这个标题真正想讲的东西。2.1 为什么只有完全二叉树才能顺序存储先给结论完全二叉树特别适合顺序存储普通二叉树不太适合。顺序存储的意思很直白把树从上到下、从左到右编号按编号把节点值放进数组下标对应的位置。根节点放下标 0第二层左边那个节点放下标 1第二层右边放下标 2以此类推。这样做的关键是一棵完全二叉树不会在中间留下空洞节点是紧凑排列的数组大小正好等于节点数。普通二叉树如果也用顺序存储会出现大量的空位。比如根节点只有右孩子没有左孩子按编号规则左孩子的那个数组位置就空着。树越斜浪费越严重。极端情况下一棵只有 3 个节点的链式斜树可能需要一个长度为 2 的幂次方的数组才能放下。所以普通二叉树通常用链式存储也就是每个节点保存左右孩子指针。而堆因为保证“无空洞”才能肆无忌惮地用数组裸存。2.2 父子下标关系左孩子 2i1右孩子 2i2数组存堆之后最重要的就是下标换算。以 0 为起始下标为例对于数组下标为i的节点左孩子下标2 * i 1右孩子下标2 * i 2父节点下标(i - 1) / 2整数除法这三条规则是整个堆实现的核心。所有上浮、下沉、建堆、排序本质上都是在做下标移动。我当初一直不理解为什么偏偏是这个公式。后来把下标写成二进制就通了父节点下标i左孩子下标是2i1右孩子是2i2。二进制里左孩子就是父节点下标左移一位再补个 1右孩子是左移一位补个 0。因为完全二叉树按层编号的规律从二进制上看天然就是这个结果。你不用记画个三层满二叉树把 0 到 6 标在节点旁边自己走一遍就能推出来。建议你拿纸画一次比背公式牢得多。一个很容易被忽略的细节是公式里的一个变体是左孩子2*i、右孩子2*i1、父节点i/2这是 1 起始下标的大小顶堆写法。两套体系都很常见但它们混用会直接翻车。在文章第 5 章我会专门列出一张对照表手写堆前最好先定死用哪一套。2.3 一个堆对象该有的基本骨架理解了批量下标规则存一个堆就变成非常简单的事。定义一个数组提供三个下标函数再维护一个表示当前堆大小的变量。下面是最基本的小顶堆骨架#include vector #include algorithm using namespace std; class MinHeap { private: vectorint 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的底层数据结构也理解了 Cpriority_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*i1 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^(h1)也就是说一共堆了几层木块可以直接对 n 取以 2 为底的对数。根据下标也能推层数0 基下标 i 对应的节点在第floor(log2(i1))层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^(h1) - 1。这不只是一个几何题结论它正是堆的数组长度和高度关系的数学本质。5. 手写堆时的高频问题与排查心得我这些年帮人 review 过不少手写堆也自己在算法题里反复踩坑。下面的问题几乎每个写堆的人都遇到过。5.1 0 下标与 1 下标哪套换算更顺手两种下标方案下标体系父节点左孩子右孩子根节点0 基(i-1)/22*i12*i201 基i/22*i2*i110 基的优势是代码和vector、list天然对齐建堆时非叶子起点是n/2 - 11 基的优势是位运算写起来好看i1、i1在执行效率和心理上都更顺但数组第一个位置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 想用大顶堆直接传lessint想用小顶堆传greaterintPython 想求最大就存相反数。日常开发里能用内置就用内置不要重复造轮子。但有两个场景我会手写堆一是需要修改堆内某个元素且要求 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足够容量插入过程就不需要反复扩容堆性能会明显好。虽然这是底层内存层面的优化但它也提醒我们堆的基本存储从来不只是“数组”两个字那么简单——你选择了连续存储就应该尊重连续存储的脾气。理解了存储才能理解性能这才是“堆的基本存储”最核心的价值。