如果你在搜索引擎里输入堆这个字大概率会同时看到三种完全不相干的东西Java虚拟机里的堆内存、操作系统里的堆区、还有我们今天要聊的数据结构堆。我在给新人做数据结构培训时发现很多人的第一个坎不是算法本身而是这个词带来的认知混乱。有人拿着数据结构的堆去排查线上内存溢出折腾一整天后回来问我为什么把进程堆大小调到8000还是报OutOfMemoryError这两个堆除了中文译名一样本质上毫无关系。这篇博文要讲的是数据结构中的堆——一种披着二叉树外衣、却能高效维护最大值/最小值的树形结构。它是优先队列的标准实现是堆排序的地基也是面试中频繁出现的TopK问题的经典解法。无论你是正在复习数据结构的在校生还是工作后需要补基础知识的开发者这篇文章都会从定义、存储、手写实现到实际选型把堆的每一个细节掰开揉碎讲清楚。尤其是那些会让你调试到怀疑人生的边界条件我会用实际踩坑的经验告诉你为什么总是报错。1. 编程世界中每一个叫堆的东西先分清再动手1.1 搜索引擎里出现的三种堆及其本质区别先说一个亲历的尴尬场景。有次我帮同事看一个问题他在IDEA里设置编译进程堆大小为8000兆结果还是报错java.lang.OutOfMemoryError截图里的异常信息写着Java heap space。他第一反应是堆不够大继续调调完还是报错最后抓我来排查。我问他你确定报错的是哪个区域吗他愣了一下说堆不就是堆吗这正是问题所在。编程世界里的堆至少有三个完全不同的含义概念所属领域本质管理方式JVM堆Java HeapJava运行时内存区域对象实例存放的内存空间垃圾回收器自动管理堆外内存Off-HeapJava NIO等JVM堆之外、由操作系统分配的内存手动管理需调用Free/close数据结构堆Heap计算机算法一种基于完全二叉树的抽象数据结构由代码实现逻辑控制JVM堆解决的是对象放哪里、何时回收的内存管理问题堆外内存解决的是绕过垃圾回收、减少拷贝的性能问题数据结构堆解决的是在动态变化的数据集中快速拿到最大或最小值的计算问题。换句话说你去搜堆可能是在搜内存配置参数可能是在搜GC调优也可能是在准备算法面试。如果这三者不区分你会在错误的方向上浪费大量时间——就像我那同事把数据结构的堆的理论套到JVM调优上方向从一开始就偏了。1.2 数据结构堆到底解决了什么问题现在我们把目光收回到数据结构堆上。一句话概括堆是一种能在O(1)时间内获取最大值或最小值、在O(log n)时间内完成插入和删除操作的数据结构。这个特性听起来平平无奇但放到实际场景中就很能打。想象你是一个游戏排行榜系统每秒都有成千上万的玩家分数在更新你需要随时知道当前分数最高的前十名。用数组存储取最大值需要扫描全部数据每次O(n)用普通二叉树最坏情况下退化成一个链表查询还是O(n)而用堆无论数据怎么变化你永远能在常数时间内看到那个最大值更新代价也就是沿着树的高度走一遍。为什么能做到这么快因为堆在结构上做了一个非常巧妙的取舍它放弃了对全序关系的维护只维护父节点一定大于或小于子节点这一条规则。这个妥协就是它高效的根本原因——数据结构的世界里你放弃的信息越多能换来的效率就越高。1.3 为什么完全二叉树是堆的物理前提堆不是随便一棵二叉树都能叫的。它必须满足两个条件第一它必须是一棵完全二叉树第二它必须满足堆序性。这两个条件缺一不可。完全二叉树的意思是除了最后一层之外每一层节点都是满的并且最后一层的节点从左到右连续地排列中间不能有空隙。这个密集排列的要求直接决定了堆可以不用传统的链式存储而用数组来承载——因为节点位置是连续的、按层编号的就像超市货架上的商品从第一排第一格开始摆摆完第一排放第二排中间不允许空货位于是货架的编号索引天然就是一个顺序列表。超市货架这个类比我一直觉得很好用。链式二叉树像是摆得七零八落的散货柜每个货位之间还挂着指针链而堆则是一个编号严格的货架你告诉售货员我要第5号位置放的东西她直接走过去就能拿到不需要沿路问路。2. 数组下标公式背后的几何直觉2.1 堆的数组化存储从树到下标的黄金映射如果一棵二叉树是完全二叉树那么我们可以从根节点开始从上到下、从左到右给它编号根节点是0它的左孩子是1、右孩子是2然后是3、4、5……以此类推。编完号之后直接把编号作为数组下标把节点值放进数组对应位置就完成了从树到数组的转换。最妙的地方在于通过两个简单的公式我们可以随时在数组和树之间来回穿梭对于下标为i的节点它的父节点下标是(i - 1) / 2整数除法它的左孩子下标是2 * i 1它的右孩子下标是2 * i 2举个例子数组[45, 32, 17, 9, 28]对应的大根堆下标2值为17的节点父节点是(2-1)/2取整等于0即根节点45左孩子是2*215超出了数组长度4说明它没有左孩子。这套公式的神奇之处在于它完全不需要指针或者引用纯粹用数学关系维系父子、兄弟之间的血缘。这套映射为什么成立你想想完全二叉树的几何结构第0层有1个节点第1层有2个第2层有4个……每层节点数翻倍。如果你把所有节点排成一行编号任何一个节点左孩子的编号一定是自身编号×2再加1因为左孩子刚好排在这棵子树接下来所有节点的中间。这个结论可以用数学归纳法严格证明但从直觉上理解就够用了——你去拿一张纸画一个四层的完全二叉树按层编号再对照公式验证几个就会发现规律非常直观。2.2 用数组存储的三大隐藏收益选择数组而不是链式存储不仅仅是能存这么简单它带来了三个实打实的好处。第一缓存友好。CPU加载数据时会把邻近的内存一次性读入高速缓存。链式二叉树的数据散落在堆区的各个角落每次访问都要去内存里随机取而数组的节点在物理上是连续的遍历时命中的是连续内存区域缓存命中率远高于链式结构。这就是为什么同样是二叉树堆的实际运行速度要比普通树快得多。第二免去空指针烦恼。链式二叉树的每个节点都要带left和right两个指针叶子节点要么设成null要么用哨兵节点任何一次忘记判空都可能引发空指针异常。数组存储则天然不存在指针越不越界完全由下标控制只要你在写代码时检查index size就行。第三空间开销极小。链式二叉树的每个节点除了数据本身还要额外存两个引用在64位JVM上通常是8字节一个。堆的数组存储则只存数据没有任何多余结构。对于千万级规模的堆这个空间差距非常可观。2.3 堆序性父大子小但兄弟之间不攀比完全二叉树解决了怎么存的问题但堆之所以有快速获取最大值的本事靠的是堆序性。以大根堆为例堆序性只有一句话**每个节点的值都不小于它的子节点。**注意这里并没有规定左孩子和右孩子谁大谁小也没有规定同一层节点之间的关系。这个松散的规则和其他数据结构形成鲜明对比二叉搜索树维护的是全局有序左子树所有节点小于根、右子树所有节点大于根中序遍历结果就是升序序列堆维护的仅仅是局部的上下级关系父亲一定压过儿子但两个兄弟之间谁也别管谁堂兄弟更不搭边。也正是这种只管上下、不管左右的约束让堆不需要像二叉搜索树那样维护严格的全局秩序从而极大降低了插入和删除的时间成本。全局有序需要O(log n)甚至O(n)的调整才能维持而局部有序往往只需要沿着一条路径交换若干次。小根堆同理只是把不小于换成不大于根节点永远是整个堆的最小值。很多人问一个大根堆的次大值在哪里答案是无法确定它可能在左子树也可能在右子树但一定在根节点的某个孩子里。理解这一点是后续理解堆排序不稳定的关键。3. 手写实现上浮与下沉堆的两条命脉3.1 上浮操作新元素鲤鱼跳龙门堆的最基本操作只有两个上浮siftUp和下沉siftDown。可以说理解了这两个操作你就理解了堆的一切。上浮发生在插入场景。往堆里插入一个新元素时我们先把元素追加到数组末尾这恰好满足了完全二叉树从左到右连续填充的要求然后它可能会破坏堆序性——新元素的父节点可能比它小。于是我们要让这个元素不断和父节点比较如果比父大就交换位置继续向上走直到它遇到一个比它大的父节点或者到达根节点为止。以大根堆为例核心代码如下Javapublic void siftUp(int k) { // k是当前节点下标初始为末尾元素下标 while (k 0) { int parent (k - 1) / 2; if (data[k] data[parent]) { // 父节点更大或相等堆序性已满足 break; } // 当前节点比父大交换然后继续向上看 swap(k, parent); k parent; } }这里有一个很多初学者会写错的细节上浮的终止条件不仅仅是k 0更重要的是那行break。如果不加break只靠k 0终止循环确实也能结束但会白白多交换几次。更严重的是如果初始化堆时数据恰好已经满足堆序性你仍然会一路交换到根把本来正确的结构搅乱。所以比较之后不满足条件就终止这个判断是上浮的灵魂。3.2 下沉操作堆顶被删后的继承者选拔下沉发生在删除场景。堆的删除永远有一个约定只能删除根节点这是由堆的功能定位决定的——你拿堆不就是来取最大或最小值的吗。删除根节点后为了继续保持完全二叉树的结构我们通常把数组末尾的元素移到根的位置然后让这个新继位者不断下沉跟它的左右孩子中较大的一个比较大根堆如果比孩子小就交换继续下沉直到它比所有孩子都大或者变成叶子为止。public void siftDown(int k) { int half size / 2; // 第一个叶子节点的下标 while (k half) { int left 2 * k 1; int right left 1; int maxChild left; // 右孩子存在且比左孩子大则最大值下标指向右孩子 if (right size data[right] data[left]) { maxChild right; } if (data[k] data[maxChild]) { break; } swap(k, maxChild); k maxChild; } }这段代码里藏着堆实现中最经典的边界陷阱。注意那个right size判断——右孩子不一定存在。完全二叉树的最后一层可能只填满了一半此时一个非叶子节点的左孩子可能存在、右孩子可能为空。如果直接索引data[right]就会触发数组越界。很多人在写二叉树程序时总是报运行时错误十有八九是栽在这种地方。再看那个half size / 2。它的奥义在于在完全二叉树中size / 2之后的下标全是叶子节点没有孩子叶子节点不需要下沉。比如size10时下标5到9都是叶子需要下沉的只有0到4k 5正好框住了非叶子节点。这个巧妙设计的好处是我们可以省去下沉函数里当前节点是否有孩子的重复判断直接用k half作为循环条件。3.3 用一个例子串起完整流程一步步手推插入跑一个完整的插入流程你会看得更清楚。假设初始空堆依次插入[32, 17, 45, 9, 28]构建大根堆。第一步插入32。数组[32]根节点完事。第二步插入17。数组[32, 17]17的父是下标0的3232大于17不需要上浮。堆已经满足。第三步插入45。数组[32, 17, 45]45的父是下标0的3245大于32交换。数组变成[45, 17, 32]。45到达根节点下标0循环终止上浮完成。第四步插入9。数组[45, 17, 32, 9]9的父是下标1的1717大于9不动。不需要上浮。第五步插入28。数组[45, 17, 32, 9, 28]28的父是下标1的1728大于17交换数组变为[45, 28, 32, 9, 17]。此时28到达下标1它的父是4545大于28终止。堆序性满足45大于28和3228大于9和1732是叶子。整个过程中每次插入最多沿着树高交换而完全二叉树的高度是O(log n)所以单次插入的时间复杂度就是O(log n)。删除根节点的流程正好相反把根拿走末尾元素顶上去然后从根开始下沉同样也是O(log n)。4. 两种建堆方式的复杂度战争O(n log n)与O(n)4.1 常规插入建堆为什么是O(n log n)如果你拿到一个无序数组最朴素的想法是把每个元素依次插入空堆从第一个元素开始逐个调用上浮操作。n个元素每次上浮最坏要走完整棵树的高度log n总复杂度就是O(n log n)。这个方案简洁易懂但存在一个明显的浪费它从空堆开始完全无视了数组中元素之间的已有关系。更关键的是上浮操作要让每个新元素从树底往上跑而大多数元素本来就该待在树的中下层让它们从最底层爬到接近自己的位置等于白白绕了远路。面试中经常有人回答建堆的时间复杂度是O(n log n)这个答案不能算全错但要看你用的是哪种建堆方式。真正的O(n)建堆靠的是下沉而不是上浮。4.2 从无序数组原地建堆为什么能做到O(n)第二种建堆方式叫自底向上原地建堆。思路是直接把无序数组看作一棵完全二叉树不需要任何额外存储数组天然就是然后从最后一个非叶子节点开始向上遍历对每个节点执行下沉操作。代码非常短public void buildHeap(int[] arr) { data arr; size arr.length; // 从最后一个非叶子节点开始向根节点方向逐个下沉 for (int i (size / 2) - 1; i 0; i--) { siftDown(i); } }为什么从size/2 - 1开始原因我们上一节说过下标从size/2开始都是叶子节点。叶子节点已经没有孩子根本不存在破坏堆序性的可能不需要处理。所以最后一个需要下沉的节点就是size/2 - 1。那为什么整体复杂度是O(n)而不是O(n log n)关键在于每个节点下沉的成本不是相等的而是和它所在的高度成正比。更妙的是越靠近树底部的节点虽然数量多但它们的下沉距离短越靠近根部的节点虽然下沉距离长但数量极少。两者相乘之后总代价被压低到了线性级别。我们做一点粗略的数学估算來建立直觉。对于一棵高度为h的完全二叉树假设有n个节点那么倒数第一层最底层大约有n/2个叶子节点不需要下沉倒数第二层有大约n/4个节点每个最多下沉1次倒数第三层有大约n/8个节点每个最多下沉2次依此类推。总代价近似为倒数第二层(n/4) × 1 n/4倒数第三层(n/8) × 2 n/4倒数第四层(n/16) × 3 3n/16后续各项不断缩小总和一个有限的常数倍乘以n严格一点说总代价是Σ (n / 2^(k1)) × k其中k从1到log n这个级数收敛到O(n)。对比一下插入式建堆每个元素都要从叶子上浮平均上浮距离是树高的一半总代价就是O(n log n)。我自己常用的一个类比是**插入式建堆是让所有人从一楼坐电梯到顶上再跑下来找位置原地建堆则是让每个楼层的人只向下走自己该走的几层。**显然后者省力得多。4.3 两种建堆方式的对比与使用场景对比维度插入式建堆自底向上原地建堆时间复杂度O(n log n)O(n)是否需要额外空间需要新数组存储不需要原地操作实现思路逐个上浮从最后一个非叶子节点开始下沉适用场景数据动态到达、逐步插入给一个静态数组要快速得到堆实际工程里如果你拿到的是一个已经存在的数组请务必用原地建堆只有在数据是流式到达、一个一个来的时候插入式建堆才是自然的选择。这一步选型之差在百万级数据量上可以差出一个数量级的耗时。5. 堆的最佳舞台TopK、优先队列与堆排序的选型逻辑5.1 海量TopK问题为什么用小根堆而不是大根堆如果面试官问你从10亿个整数中找出最大的100个你可能会本能地想既然是找最大的那我用大根堆啊堆顶就是当前最大。思路没错但内存代价完全不对。我们稍微算一笔账10亿个整数全放堆里仅存储整数本身就需要大约4GB内存这还没算数组扩容的余量开销。在实际系统中你要处理的数据规模往往超过可用内存。正确的做法是用一个容量为K这里是100的小根堆然后遍历数据流只做一件事——如果当前元素比堆顶当前100个候选里最小的那个大就把堆顶换掉新元素下沉重新选出100个里最小的当堆顶。这个方案的妙处在于小根堆的堆顶恰好是当前100个最大元素的门槛。任何比门槛小的元素直接忽略比门槛大的替换掉门槛堆里始终维持着迄今为止最大的K个。遍历完所有数据后小根堆里装的就是全局最大的100个而且堆顶就是这100个里最小的那个。复杂度也很漂亮遍历n个元素每次和堆顶比较是O(1)只有需要替换时才做一次O(log K)的下沉。总复杂度O(n log K)内存开销只有O(K)。当K远小于n时这个方案比全部排序取前K个高效太多也比维护大根堆省太多内存。这里必须强调一个容易记反的结论**找最大的K个用小根堆找最小的K个用大根堆。**记法很简单——堆顶永远是门卫是我们关心的那条分界线。找最大时我们关心谁有资格进入候选集门槛就是候选集里最小的找最小时同理。5.2 优先队列堆成为无数算法级组件的基石堆最常见的工程形态是优先队列。优先队列的本质是一个队列但出队顺序不是先进先出而是优先级高的先出。你可以把优先队列看作一个自动排序的漏斗无论什么顺序塞进来吐出来的永远是目前优先级最高的那个。这个能力在真实系统里几乎无处不在。操作系统的任务调度器用优先队列来选择下一个要运行的进程网络框架的定时器用优先队列管理海量超时事件堆顶就是最近要触发的那一个Dijkstra最短路径算法、Prim最小生成树算法、A*寻路核心依赖的数据结构全部是优先队列。图算法里的每一次选一个当前距离最近的未访问节点就是在做一次堆顶取出操作。Java里的PriorityQueue、Python里的heapq、C里的priority_queue底层实现都是堆。很多同学在面试手撕算法题时遇到动态取最大/最小的套路第一反应就是优先队列——这个直觉是正确的。但要注意优先队列不是万能的排序工具它只保证按优先级出队如果你把元素全部入队再全部出队得到的确实是有序序列这个过程本质上就是堆排序。5.3 堆排序永远O(n log n)的不稳定排序堆排序的逻辑一句话就能讲完用原地建堆把数组变成大根堆然后不断把堆顶最大值和数组末尾交换同时把堆的有效长度减一再对新的堆顶做下沉。重复n-1次数组就是从小到大有序的。堆排序有三个鲜明的特点。第一时间复杂度稳定地是O(n log n)无论输入数据是正序、逆序还是乱序它都会老老实实地建堆、交换、下沉。第二空间复杂度是O(1)原地操作不像归并排序需要额外数组。第三它是不稳定的排序。关于不稳定这一点很多教程只是一笔带过我在这里展开一下。假设你有两个相等的元素A和BA在B前面堆排序在把堆顶往末尾扔的过程中会反复跨越多个位置交换元素。相等的元素在交换中可能被移动到对方后面打破原有的相对顺序。比如数组[3a, 3b, 1]建堆后3a和3b的位置可能已经互换后续交换又可能把它们拉到更远的位置。如果你需要在排序时保持相同元素的相对顺序请改用归并排序或稳定版本的快速排序如果只是要一个稳定的O(n log n)且不要求稳定堆排序是很省内存的选择。5.4 别把堆当万金油在一堆数据里凑数的正确姿势热搜词里有一条很微妙在一堆数据里凑出一个数比如给定一个数组和一个目标值找出数组中两个数之和等于目标值的下标。遇到这类问题千万不要条件反射地掏出堆来。两数之和的最优解是哈希表遍历数组每看到一个数就去哈希表里查目标值减去当前数是否存在时间复杂度O(n)。三数之和一般做法是先排序再用双指针在有序数组上收缩区间时间复杂度O(n²)。堆在这里帮不上什么忙——堆擅长的是动态维护极值而凑数问题需要的是快速查找是否存在某个补数这是哈希表的战场。选数据结构的本质是匹配问题的抽象操作。问自己三个问题你需要频繁获取最大值或最小值吗需要动态地插入和删除吗数据规模有多大如果取极值是核心操作堆就是不二之选如果是查找某个值是否存在哈希表更合适如果是求有序序列排序加双指针才是正路。工具没有好坏只有合不合适。6. 写堆代码最容易翻车的几个瞬间与排查思路6.1 链式二叉树的空指针、越界与递归栈溢出先回答一个高频疑问我写二叉树程序时为什么总是报运行时错误这个报错背后通常是三个原因。第一个原因是空指针。如果你用传统的链式结构实现二叉树访问左孩子之前不判空遇到叶子节点就崩。排查链式二叉树的空指针我的习惯是先画一棵三层的小树把每个节点的左右子树画全然后在代码里逐步走一遍看每一步访问的是不是确实存在的节点。大多数空指针都源于想访问的孩子根本不存在。第二个原因是数组越界。这个发生在用数组实现堆时原因我们在下沉操作里分析过右孩子可能不存在直接索引就崩了。排查方法是打印当前节点下标、堆大小、左右孩子下标手动验证left size和right size两个条件。第三个原因是递归深度过大。链式二叉树如果退化成链状比如插入有序数据时递归遍历的深度会达到n直接触发方法栈溢出。排查方法是加上深度打印或者改用迭代遍历。而数组实现的堆没有这个问题——因为它的结构被完全二叉树约束住了深度天然是log n。6.2 用错堆概念排查内存溢出的经典弯路再回到文章开头的故事。那位同事把IDEA编译进程堆调到8000兆还报java.lang.OutOfMemoryError问题出在哪首先OutOfMemoryError是个笼统的异常族下面有多个子类型Java heap space表示JVM堆空间不足GC overhead limit exceeded表示垃圾回收器几乎一直在回收但收效甚微Metaspace表示方法区元数据空间不足还有直接内存不足、栈溢出等。不同类型的报错排查方向完全不同。其次盲目调大-Xmx参数不一定能解决问题。如果你的程序存在内存泄漏堆调得再大也会被慢慢耗尽如果你的程序在创建超大数组瞬间需要的连续空间超过堆大小调大堆倒是可能有帮助如果早就是GC overhead limit exceeded问题往往在于活跃数据太多或GC算法配置不当而不是堆太小。正确排查顺序是先用jstat -gcutil看各内存区域的使用率和GC频率再用jmap或jcmd生成堆转储文件heap dump然后用MAT或VisualVM分析到底是哪个对象占用了大量内存是谁在引用它。最后才谈得上调整参数。这里想强调一个通用经验排查问题前先搞清楚你面对的是哪一层的东西。数据结构的堆用代码控制逻辑JVM的堆用参数控制内存两者连理论体系都不共用拿着数据结构的思维去调JVM参数等于拿着菜刀修电路——工具确实锋利但方向错了。6.3 搜索二叉树与堆的混淆全局有序与部分序的差异最后一个高发混淆点是把二叉搜索树和堆搞混。两者都是二叉树都涉及节点之间的大小关系但规则完全不同。二叉搜索树BST维护的是全局有序左子树所有节点小于根右子树所有节点大于根中序遍历结果是严格的升序序列。它的核心操作是搜索时间复杂度依赖于树的高度但如果插入顺序不好比如升序插入树会退化成链表搜索变成O(n)。所以工程上才需要AVL树、红黑树这种自平衡版本。堆维护的是部分有序只有父节点一定不小于子节点这一条规则左右子树之间、同一层的兄弟之间没有任何大小约定。它的核心操作是取极值得益于完全二叉树的紧凑排列它的高度永远是对数的不会退化。两者的典型使用场景完全不同需要频繁查找某个特定值是否存在用二叉搜索树或哈希表需要不断获取最大最小值用堆。面试里如果让你设计一个支持插入、删除、取最大值的数据结构堆就是标准答案如果让你设计一个支持插入、搜索、按序遍历的数据结构二叉搜索树才登场。6.4 手写堆时我的几条防御性编程习惯最后分享几个我踩坑之后养成的小习惯可能帮你省下大把调试时间。测试时用小数据集并且打印每步状态。我建堆时会用一个只有5到7个元素的数组每次交换都打印数组内容和下标关系用眼睛确认堆序性。等小数据集完全正确再上大数据压力测试这样能把边界问题隔离在最小范围。严格区分堆大小和数组容量。堆的size是有效元素个数数组的capacity是分配的内存长度。所有比较都用size不要稀里糊涂用data.length否则你会在数组还有空位的假象下访问到无效数据。先实现、再证明、后优化。先老老实实写出上浮下沉的循环版本确认正确再去想着用位运算、减少交换次数等方式优化。很多所谓的高性能堆在正确性还没保证时就动手优化最后bug和性能问题混在一起非常难查。数据结构这个东西光看教程不写代码就像看了菜谱不下厨——你记住了所有步骤但真正起火颠勺时才会发现锅比想象中重。找一台电脑开一个IDE把大根堆、小根堆、原地建堆、优先队列各写一遍故意制造几次越界和空指针亲手解决它们。这个过程走完你对堆的理解会比刷二十道题都扎实。