堆这个东西我在面试里问过的人没有一百也有八十能把“堆”真正讲透的确实不多。很多人背下了“父节点大于子节点”这句话但一让手写个堆排序就卡壳还有一部分人会用Java的PriorityQueue却说不清为什么TopK问题要拿小顶堆来解。如果你也有类似的模糊地带这篇文章应该能帮你把整块拼图补上。我会从堆的本质开始把存储结构、核心操作、应用场景、语言实现和常见坑全串一遍最后给出一套可以直接拿去用的代码模板和排查思路。不管你是准备面试、做课程设计还是在工作中遇到海量数据排序、定时器调度这类场景这篇都值得你花十几分钟读完整。1. 先搞清楚堆到底是什么1.1 堆的两个硬性条件结构 序堆不是一个独立的数据结构它在物理上就是一棵完全二叉树只不过这棵二叉树额外满足一条“序”的规定。完整地说堆必须同时满足两个条件结构条件它必须是一棵完全二叉树。所谓完全二叉树就是除了最后一层之外每一层都是满的并且最后一层的节点都靠左排列。这个条件决定了堆可以用数组来存储而不需要存左右指针。序条件任意节点的值必须大于等于大顶堆或小于等于小顶堆它的所有子孙节点的值。很多人会把堆和“二叉搜索树”搞混。这里我强调一下二叉搜索树要求左子树所有节点小于根、右子树所有节点大于根这是一种全局的偏序关系而堆只要求父节点和子节点之间有大小关系至于左儿子和右儿子谁大谁小完全不关心。所以堆的查询能力比BST弱它只在“获取最大/最小值”这个方向上做到极致。用人话说如果你把大顶堆想象成一个公司的职级体系老板总是最大的那个但底下两个平级部门谁强谁弱无所谓只要别超过老板就行。这种“局部有序”的松散约束正是堆能高效完成插入和删除的原因——它不需要像BST那样频繁旋转或重排来维持全局有序。1.2 数组怎么存一棵完全二叉树因为完全二叉树的形态是确定的我们可以直接用一个一维数组来存它不需要链表节点。数组下标和树的位置之间有非常固定的映射关系。假设数组下标从0开始那么对下标为 i 的节点左孩子下标2 * i 1右孩子下标2 * i 2父节点下标(i - 1) / 2如果下标从1开始比如某些教材和C语言实现左孩子下标2 * i右孩子下标2 * i 1父节点下标i / 2这两套体系在代码里很容易混。我在面试时经常看到候选人写着写着突然卡住就是因为一会儿用0基一会儿用1基。我的建议是选定一种全篇统一。我自己写代码习惯用0基因为Java、Python、C的标准库容器都是0基跟着语言走最不容易出错。数组存储带来的另一个好处是缓存友好。完全二叉树用数组连续存放后访问子节点其实就是内存里的相邻偏移CPU缓存的命中率比指针式的二叉树高很多。这也是为什么工程实现里优先队列几乎都用数组堆而不是链式树。注意判断一个数组是不是合法的堆不需要额外建树。直接从最后一个非叶子节点往前遍历逐个检查每个节点是否满足父大于子或父小于子即可。最后一片叶子因为压根没有孩子天然满足条件不需要检查。1.3 堆不是“有序数组”别搞混这是一个非常常见的误区。堆只保证堆顶元素是全局最大或最小但绝不是说数组整体按大小排好了序。举个例子一个合法的大顶堆可能是这样的数组[9, 5, 8, 3, 4, 6, 7]它对应的一棵完全二叉树是9 / \ 5 8 / \ / \ 3 4 6 79是最大值但8排在5后面6和7在第三层。你从这个数组里得不到一个全局升序或降序的序列。这个特性太重要了很多人写堆排序时以为只要把数组调整成堆然后遍历一遍就完事结果发现顺序是乱的——这很正常因为你拿到的只是堆序不是全局序。堆的序是“沿着根到叶子的路径上有序”而不是“从左到右有序”。只要父节点大于子节点具体哪个孩子大完全随意。理解这一点你才能理解为什么堆排序必须要“反复把堆顶拿走再重新调整”才能得到有序序列。2. 堆的核心操作背熟这三个就够了堆的所有操作本质都是围绕两个基本动作展开的上浮sift up和下沉sift down。加上建堆时的自底向上调整一共三大块。我建议你亲手各写一遍光看不写等于没学。2.1 上浮shift up插入元素的标准动作向堆里插入一个新元素标准流程是把新元素追加到数组的末尾这相当于在完全二叉树的最后一个位置加了一个叶子节点。从新元素开始不断和它的父节点比较。如果是大顶堆新元素比父节点大就交换然后继续往上直到走到根节点或不需要交换为止。这个操作的代价是 O(log n)因为完全二叉树的高度是 log2 n 级别最坏情况下一路交换到根。我自己写了一个固定容量的大顶堆当演示模板插入逻辑是这样的public class MaxHeap { private int[] data; private int size; private int capacity; public MaxHeap(int capacity) { this.capacity capacity; this.data new int[capacity]; this.size 0; } public void offer(int val) { if (size capacity) { throw new IllegalStateException(堆已满); } data[size] val; // 先放到末尾 shiftUp(size); // 再上浮 size; } private void shiftUp(int index) { int temp data[index]; while (index 0) { int parent (index - 1) / 2; if (data[parent] temp) { data[index] data[parent]; // 父节点下移 index parent; } else { break; } } data[index] temp; } }这里有个小技巧我先把待插入的值存到 temp 里然后循环里只做单方向的赋值而不是每次交换两个数。这样能减少约一半的数组写入次数数据量大时性能差异还是很明显的。这个技巧在排序算法里叫“挖坑法”在堆调整里同样适用。2.2 下沉shift down删除堆顶的关键操作删除堆顶元素也就是取出当前最大/最小值时不能直接把数组后面的所有元素往前挪那样会破坏完全二叉树结构。标准做法是把数组最后一个元素的值赋给堆顶。弹出最后一个元素size 减一即可。从堆顶开始不断把当前节点和它的左右孩子中较大的那个大顶堆进行比较如果孩子更大就交换然后继续下沉直到叶子节点或无需交换为止。下沉同样也是 O(log n) 的复杂度。代码长这样public int poll() { if (size 0) { throw new IllegalStateException(堆为空); } int top data[0]; data[0] data[size - 1]; // 末尾顶上来 size--; shiftDown(0); // 从根往下调整 return top; } private void shiftDown(int index) { int temp data[index]; int half size / 2; // 最后一个非叶子节点的下界 while (index half) { int child index * 2 1; // 默认取左孩子 int right child 1; if (right size data[right] data[child]) { child right; // 右孩子更大换右 } if (temp data[child]) { data[index] data[child]; index child; } else { break; } } data[index] temp; }注意 shiftDown 的终止条件不是 index size而是 index size / 2。因为当 index 大等于 size/2 时它已经是叶子节点了叶子节点没有孩子自然不需要再下沉。这个边界条件也是很多人写错的地方少写一个等号就可能在循环里越界访问。2.3 建堆为什么自底向上调整最省时间把一个无序数组变成堆有两种思路。第一种最笨的办法一个空堆把数组元素逐个 offer 进去。每个元素 O(log n)总复杂度 O(n log n)。这个思路虽然简单但不够高效。第二种办法直接在原数组上从最后一个非叶子节点开始逐个执行 shiftDown。这叫做“自底向上建堆法”时间复杂度是 O(n)。为什么能到 O(n)你可以这么想下沉操作的总代价和所有节点的高度之和成正比。完全二叉树中绝大多数节点都集中在底部越靠近底部高度越小。算下来所有节点的高度和是 O(n)而不是 O(n log n)。具体证明用等比数列求和就能推出来我不在这里展开但记住结论自底向上建堆是 O(n)自顶向下插入建堆是 O(n log n)。最后一个非叶子节点的下标怎么找很简单大小为 size 的堆最后一个元素的下标是 size - 1它的父节点就是最后一个非叶子节点。0基下标下父节点是 (size - 1 - 1) / 2 size / 2 - 1。所以从 size / 2 - 1 开始一直递减到 0逐个 shiftDown。public void buildHeap(int[] arr) { this.data arr; this.size arr.length; this.capacity arr.length; for (int i size / 2 - 1; i 0; i--) { shiftDown(i); } }提示如果堆的容量可能超过数组长度buildHeap 前先扩容。我踩过这个坑数组满时还在 buildHeap结果 shiftDown 过程里越界。3. 堆的经典应用场景堆在工程里的出场率远超你的想象。这里的每一个场景不是面试题而已而是真的在系统里活着的代码。3.1 优先队列堆最常见的马甲优先队列PriorityQueue是堆最直接的工程形态。Java 的java.util.PriorityQueue、Python 的heapq、C 的priority_queue底层全部是堆。优先队列解决的问题是按照优先级出队而不是按照入队顺序出队。一个典型的例子是操作系统进程调度里的“饥饿”问题。如果只用 FIFO 队列排在长任务后面的短任务可能要等很久。用优先队列按执行时间排序短任务就能先跑系统的平均响应时间立刻降下来。再比如最短路径算法 Dijkstra每次都要从候选集合里取“当前距离最小”的节点。如果每次都用数组线性扫描复杂度是 O(V²)图一大就爆炸。换成小顶堆来维护“未确定最短路径的节点集合”每次取最小值的代价变成 O(log V)整体复杂度立刻降为 O((VE) log V)。堆在这个场景里不是优化而是让算法具备可行性的关键。3.2 TopK 问题海量数据里挑大个面试高频题“从 100 万个整数里找出最大的 10 个”堆的标准解法是维护一个大小为 K 的小顶堆。为什么是小顶堆因为你要找最大的 K 个那堆里应该存的是“当前已经找到的最大的 K 个”为了判断新来的元素能不能挤进去你需要知道这 K 个里最小的是谁也就是堆顶。如果新元素比堆顶大就弹掉堆顶、插入新元素。如果你用大顶堆堆顶是当前最大的那新元素永远没法把堆顶挤出去因为堆顶总是大于新元素除非新元素破纪录你最后只会得到“最大的那个数”而不是最大的 K 个。这个“为什么用反了”的问题我在面试中几乎每次都会追问能答清楚的人真的不多。流程画成步骤就是先读入前 K 个元素建一个小顶堆。遍历剩余元素如果比堆顶大就 poll 掉堆顶offer 这个新元素。结束后堆里的 K 个元素就是全局最大的 K 个。整体时间复杂度 O(n log K)内存占用只需要 O(K)。100 万个整数K10根本不需要把数据全部加载进内存——这在处理流式数据或超大文件时是巨大的优势。3.3 堆排序原地排序但细节多堆排序的思路很直白先建堆然后反复把堆顶最大/最小值换到数组末尾把末尾“封存”起来再对剩余部分做 shiftDown。它有两个显著特点原地排序额外空间复杂度 O(1)不依赖递归栈。不稳定因为堆排序存在“父子交换”这种远距离的位置变动相等元素的相对顺序可能被打乱。这是它对比归并排序的硬伤。代码模板我直接给出public void heapSort(int[] arr) { // 1. 建堆 int n arr.length; for (int i n / 2 - 1; i 0; i--) { adjust(arr, i, n); } // 2. 逐个取出堆顶 for (int i n - 1; i 0; i--) { int temp arr[0]; arr[0] arr[i]; arr[i] temp; adjust(arr, 0, i); // 注意 i 是新的堆大小 } } private void adjust(int[] arr, int index, int heapSize) { int temp arr[index]; while (index * 2 1 heapSize) { int child index * 2 1; if (child 1 heapSize arr[child 1] arr[child]) { child; } if (arr[child] temp) { arr[index] arr[child]; index child; } else { break; } } arr[index] temp; }堆排序的时间复杂度稳定在 O(n log n)无论最好、最坏还是平均这点比快排强。但现实中快排因为有更好的缓存局部性和更少的元素交换常数因子远小于堆排序所以工程上的通用排序基本都是快排的改良版。堆排序的用武之地主要在对时间稳定性要求极高、且不想用额外空间的嵌入式环境里以及作为优先队列的附属技能出现。3.4 更多场景定时器、中位数、合并有序链表堆的性能上限是 O(log n)所以凡是需要“动态维护最值”的场景堆几乎都是默认答案。定时器系统很多定时任务框架比如 Java 的 DelayQueue、Netty 的 HashedWheelTimer 内部设计会用小顶堆按“下次触发时间”排序每次取堆顶就是要执行的任务。数据流中位数维护一个大顶堆存较小的一半一个小顶堆存较大的一半动态保证两个堆的大小差不超过一。取中位数时直接看两个堆顶就行。合并 K 个有序链表把 K 个链表的当前头节点放进小顶堆每次弹出最小的然后把它所在链表的下一个节点入堆。复杂度 O(N log K)比两两合并整整高一个维度。这些场景的共同点是数据在动态变化你不能像静态排序那样先全部排好再一次性读取。堆的插入和删除都是 O(log n)恰好适合这种“边来边取”的节奏。4. 语言内置实现与选型指南很多情况下你不需要自己手写堆直接用标准库就行。但不同语言的标准库行为差异很大用错一个参数就是整段崩溃。4.1 JavaPriorityQueueJava 的PriorityQueue默认是小顶堆。如果要大顶堆需要传一个反转的比较器PriorityQueueInteger minHeap new PriorityQueue(); PriorityQueueInteger maxHeap new PriorityQueue((a, b) - b - a);这里有个经典坑(a, b) - b - a在极端数值下可能溢出。比如 a 是 -21亿b 是 21亿b - a 直接溢出成正数比较器就会返回一个错误的结果。更稳妥的写法是(a, b) - Integer.compare(b, a)。写底层框架的哥们儿从来不直接做减法比较就是这个原因。如果你存的是自定义对象比如任务带时间戳和优先级记得比较器的规则要能处理字段相等的情况否则可能出现元素明明相同却被判定为“既不大于也不小于”的尴尬局面。另外PriorityQueue 不是线程安全的多线程场景要加锁或使用PriorityBlockingQueue。Java 的 PriorityQueue 内部用 Object 数组存储元素但数组大小是动态扩容的。扩容策略是小于 64 时双倍扩容否则 1.5 倍。这个细节在内存敏感的低延迟场景里值得注意——频繁扩容会触发数组拷贝和 GC 压力。4.2 PythonheapqPython 的heapq模块默认只支持小顶堆且它操作的是普通列表不是独立的容器类。import heapq data [3, 1, 4, 1, 5] heapq.heapify(data) # 原地建堆O(n) heapq.heappush(data, 0) # 入堆 min_val heapq.heappop(data) # 弹出最小值如果想用大顶堆有个小技巧入堆时存取反值即-value出堆时再取一次反。虽然有点绕但在 Python 里这是最简洁的大顶堆写法。heapq还有一个隐藏能力nlargest和nsmallest。它们内部会根据 K 的大小自动选择最优策略如果 K 相对 n 很小就用堆如果 K 接近 n就直接排序。所以你只需要写heapq.nlargest(10, big_list)不用自己折腾堆逻辑代码可读性还高。4.3 Cpriority_queueC 的priority_queue默认是大顶堆且不支持取堆顶元素以外的遍历方式也不支持删除非堆顶元素。它适配三个模板参数其中比较器需要传一个仿函数或者greaterT#include queue using namespace std; priority_queueint maxHeap; // 大顶堆 priority_queueint, vectorint, greaterint minHeap; // 小顶堆C 的 priority_queue 不像 Java 那样可以随便迭代也不提供修改任意元素的操作。所以如果你要“改堆中某个任务的优先级”需要自己封装一层要么用 map 记录元素和索引的对应关系要么直接删掉重建。这个限制在 C 工程里经常让人头疼但换个角度想它的内存占用和性能开销也是三种语言中最可控的。我做了一个简表方便你快速选型语言默认堆型大顶堆写法特殊能力线程安全Java小顶堆传反转比较器无内置 key 更新非线程安全Python小顶堆存负值nlargest/nsmallest无锁C大顶堆传 greater无法遍历/改值非线程安全4.4 手写堆 vs 内置容器怎么选我的经验是能用内置容器绝不手写堆。三个原因内置容器经过大规模测试边界问题少内置容器的性能通常已经被极致优化手写很难超过代码可读性和维护性完全不在一个层次。但有些场景必须手写堆需要堆中元素的索引比如 Dijkstra 里要快速更新某个节点的距离时要“改堆内元素”。需要对堆进行堆合并比如可并堆左式堆、斜堆、二项堆。面试或考试中明确要求实现底层。如果是课程设计或学习练习我建议手写一版哪怕只是为了验证你对 shiftUp/shiftDown 边界条件的理解。5. 常见踩坑现场与排查思路最后这部分我把我见过的以及自己踩过的坑集中整理一下。每一条都是我实际遇到过并花不少时间定位过的建议你存下来当备忘录用。5.1 下标从 0 还是从 1混用导致越界这是新手最容易踩的坑。在 shiftUp 和 shiftDown 里父节点和子节点的下标换算公式0基和1基完全不同。如果你在插入时用parent (index - 1) / 2在建堆时又突然用parent index / 2堆在特定数据下可能不崩但会在某些角落位置产生错误的结果。排查方法是找一个小数组把每次交换后的数组打印出来对照完全二叉树画一下。不用多画两遍就矫正过来了。我的习惯是统一用 0 基parent (i - 1) / 2left 2*i 1right 2*i 2。如果你在 Java 或 Python 环境下工作这是最自然的选择。5.2 大顶堆小顶堆选反了TopK 问题里选反堆型的概率极高。记住一句话找最大的 K 个用小顶堆找最小的 K 个用大顶堆。原因我在 3.2 里已经讲透了——堆顶始终是“当前候选集里最弱的那个”新数据打败它它才出局。这个思路在堆实现的优先队列里也一样如果按时间戳最小优先就用小顶堆按价格最大优先就用大顶堆。如果测试时发现堆里装的是“最小的 K 个”不用怀疑堆型选反了。5.3 shiftDown 的循环边界写错shiftDown 里最经典的 bug 是少写一个等号或者忘记判断右孩子是否存在。我见过一种情况循环条件写成了while (index size)然后分叉到计算 child 时child 可能超出数组长度直接抛 ArrayIndexOutOfBoundsException。建议统一写成while (index size / 2)这样能保证当前节点一定有至少一个孩子。然后在选择左右孩子时先判断右孩子是否越界if (child 1 size ...)。这套组合基本不会再出错。5.4 定时器任务堆的“删除中间节点”问题工程上经常遇到“我要取消某个任务但这任务不在堆顶”。普通堆不支持删除任意节点因为删除后需要重新调整并且你都不知道这个节点在数组的哪个位置。解决方法是加一个“延迟删除”标记从堆中拿出的元素如果不是有效任务就直接丢弃继续取下一个。这就是 Kafka 定时器、很多网络框架里都会用到的 lazy deletion 思路。你可以额外用一个哈希表记录“已取消任务的下标”等它到堆顶时统一清理。5.5 堆排序的不稳定排序结果可能违反直觉堆排序的不稳定性体现在元素会被远距离交换。例如[2a, 2b, 1]在大顶堆排序时可能把靠前的 2a 换到数组尾部最后输出是1, 2b, 2a两个 2 的相对顺序变了。如果你做的是对象数组排序而且依赖相等元素的顺序比如按时间排序时希望批次 ID 相同的保持输入顺序就不能用堆排序。这种情况要么换稳定排序要么给比较器增加一个“序列号”字段作为次级排序键人为制造确定性。5.6 所谓“堆空间不足”和堆结构混淆很多 Java 开发者听到“堆外内存”“堆空间不足”时第一反应是数据结构和它有什么关联。这其实是两个完全不同的概念数据结构里的“堆”是一种树形结构而 JVM 的“堆”是存放对象实例的内存区域。两者没有任何直接关系只是中文都叫“堆”而已。如果你在排查 OutOfMemoryError别在本博客里找答案那是内存管理的范畴。6. 最后的建议怎么把堆真正学好写技术分享这么多年我对“学一个数据结构”有一套自己的标准能不能在完全不看资料的情况下十分钟内手写出建堆、入堆、出堆三个方法并保证边界无误。如果你能达到这个水平面试题里的堆题目基本拦不住你如果还差一点建议你按下面的方式练一遍第一画图。不用工具拿张白纸画出 15 个节点的完全二叉树标上数组下标然后模拟一遍自底向上建堆、插入、删除的全过程。这一步能让堆的运行机制在你脑子里扎根。第二背模板。把本文里的 MaxHeap 代码亲手敲一遍敲完改写成 MinHeap再改写成泛型。折腾三次后你对堆的四个边界条件空堆、单节点堆、满堆、下标越界前那一刻会有肌肉记忆。第三做题验证。去刷几道经典的堆问题数组中的第 K 个最大元素、前 K 个高频元素、数据流的中位数、合并 K 个升序链表。不要用 JLibrary 一把梭至少要自己在脑海里推演一遍堆的操作过程再用内置容器验证结果。题目通过只是最低要求能讲清楚“为什么用这个堆型、为什么这样调整”才算真正过关。堆的美妙之处在于它的逻辑其实很简单复杂的是各种边界和细节。一旦你跨过“能写出来”这个坎后面再看优先队列、堆排序、TopK 这些问题会觉得它们就像同一个工具箱里的不同扳手——你要做的只是在合适的时机拿起合适的那把。把这些边界条件梳理清楚之后我对堆的恐惧早就消失了希望你也能在几次主动调试之后找到这种“原来如此”的掌控感。