看到“堆”这个词，很多程序员都会愣一下，因为它在不同场景里代表的东西完全不一样。做数据结构的课程作业时，老师让你手写堆排序；深夜排查服务内存暴涨时，你用jmap看的是Java堆；写C语言时，malloc分配在堆上；刷面试题又会看到堆外内存、DirectBuffer、编译器堆空间不足这些词。更别提面试时，主考官轻描淡写地来一句“用堆实现一个TopK”，而你脑中还在纠结到底该用大顶堆还是小顶堆。
这篇文章准备把这些概念一次性拆开讲清楚：数据结构里的堆、进程内存里的堆、语言运行时里的堆外内存，以及围绕堆的基础操作和实战方法，全部带过一遍。适合正在学数据结构的在校生、准备算法面试的开发者，以及被内存问题折腾过、想彻底搞懂“堆和栈”到底差在哪的工程师。内容不追求讲得特别深，但会尽量把“为什么这样设计”“为什么用这个堆”这类底层逻辑讲明白，帮你以后再看到带“堆”字的概念都能立刻对号入座。
1. 堆的两副面孔：数据结构和内存区域的区别
1.1 同一个词，两种完全不同的体系
先说一个不少人踩过的坑：数据结构里的“堆”和操作系统里的“堆区”，其实只是恰好叫同一个名字，在英文里也是不同的词源。数据结构里的堆叫Heap，最初来源于“堆在一起的东西”，指的是一种按特定顺序组织的树形结构；内存管理里的堆区也叫Heap，指的是动态内存分配所在的区域，概念来源是“一堆空闲内存块”这个印象。
但为什么偏偏都叫Heap？有一个流传很广的说法是：早期的内存分配器把空闲内存块像“堆叠”起来管理，所以就叫heap。再加上数据结构里二叉堆通常用数组存放，数据也是“堆叠”在数组里的，名字就这么混着叫开了。这个巧合在面试中经常把人绕晕：面试官先问“堆排序的原理”，接着又问“进程的内存布局里堆和栈有什么区别”，看起来是一个知识点，实际上需要你用两套知识体系去回答。
把这两套体系分开记是学习的第一步。数据结构中的堆解决的是“如何高效取最大/最小元素”的问题，对应的操作有插入、删除、建堆；内存管理中的堆解决的是“程序运行时如何动态申请和释放内存”的问题，对应的概念有malloc、垃圾回收、内存泄漏、堆外内存。两者之间没有公式上的直接联系，但彻底理解之后你会发现，它们的核心思想都是“对一块区域做高效管理”。
1.2 为什么堆这么好用，却总让人犯迷糊
如果要我总结，大概有三个原因。
概念多而近。大顶堆、小顶堆、优先队列、堆排序、堆外内存、编译器的堆空间不足……这些词放在一起，既像父子又像兄弟，没有一条主线确实容易晕。建议初学者先抓一类：优先掌握数据结构堆，因为它是算法题里最常出现的考点，等有了手感再学内存堆。
维度跨度大。从数据结构跳到操作系统，再从理论分析跳到实际排障，每一步都要求读者换一种视角。我之前带过几个实习生，在纸上写堆排序手到擒来，但一看到“Error: java.lang.OutOfMemoryError: Java heap space”就以为是自己写的堆出了问题，实际上两者八竿子打不着。
资料里默认你什么都会。很多文章上来就讲数组下标i的左孩子是2i+1，却没说清楚下标从0开始还是从1开始；讲优先队列时，默认你已经知道为什么Python的heapq是小顶堆，而C++的priority_queue却是大顶堆。这篇文章会把容易默认跳过的细节补上，让你以后看任何资料都能秒懂对方在说什么。
2. 算法世界的堆：类别、存储方式和经典应用
2.1 大顶堆和小顶堆：不仅仅是“根最大和根最小”
数据结构里的堆，最常见的是二叉堆。二叉堆必须满足两个条件：第一，它是一棵完全二叉树，也就是除了最后一层，其它层必须填满，且最后一层的节点都靠左排列；第二，节点和子节点之间满足堆序性，通常分为大顶堆和小顶堆。
大顶堆要求每个父节点的值都大于等于它的子节点，因此堆顶一定是整个堆的最大值；小顶堆则相反，堆顶是最小值。这里容易产生一个误区：有人会把堆和二叉搜索树混在一起，以为左子树一定比右子树小。实际上堆的兄弟节点之间没有大小约束，只有父子之间满足堆序性。你可以把大顶堆理解成一个“家长永远比孩子拿得多”的组织，但同一层之间谁拿得多谁拿得少，完全随意。
堆的平衡性来自完全二叉树。因为树的高度始终维持在log2(n)级别，所以插入、删除堆顶元素都只需要O(log n)的时间。这个复杂度优势是堆在算法问题中广泛使用的根基。你可以对比一下普通数组：找最大值要O(n)，插入要移动大量元素；用二叉堆则能在动态数据流中始终以很小的成本维护“当前最大/最小”的信息。
2.2 数组存储堆：三个必须牢记的下标公式
二叉堆一般不用链表节点表示，而是用数组，原因就在于完全二叉树的结构天然适合连续存储。如果你用节点指针反而会浪费大量空间，还要维护额外的节点对象，所以堆的实现几乎都会基于数组。
假设根节点存放在数组下标0的位置，那么对于下标i的节点：
- 父节点下标：parent(i) = (i - 1) / 2
- 左孩子下标：left(i) = 2 * i + 1
- 右孩子下标：right(i) = 2 * i + 2
如果根节点从1开始存放，公式会变成：
- 父节点下标：parent(i) = i / 2
- 左孩子下标：left(i) = 2 * i
- 右孩子下标：right(i) = 2 * i + 1
很多人面试手写堆时容易在这里翻车。写代码之前，先明确数组的0号位置是否参与堆的存储。如果从0开始，那么左孩子是2i+1，不是2i；如果从1开始，则0号位置要么空着，要么只作为占位符存在。两套公式一旦混用，插入删除时会出现大量越界和找不到父节点的问题。
我自己更推荐在实际刷题时统一用“0号位参与存储”的习惯，因为Python的heapq内部就是这样的逻辑，C++的priority_queue底层容器vector默认也是从0开始。如果你默认Java、C++常用写法没问题，切到Python时也顺理成章。
2.3 插入和删除：上浮与下沉，堆操作的核心灵魂
堆的插入操作并不复杂：把新元素追加到数组尾部，然后“上浮”。上浮的意思是，不断拿当前节点和父节点比较，如果违反了堆序性就交换位置，直到到达堆顶或者满足堆序。这个过程很像在一个已经排好队的队伍里插入一个新成员，如果新成员比前面的领导级别还高，就一路往前换。
删除堆顶元素则是另一个思路：先把堆顶元素和数组最后一个元素交换，然后让这个临时堆顶“下沉”。下沉时每次和左右孩子中较大/较小的那个比较，一旦不满足堆序就交换，持续走到叶子节点。之所以选数组最后一个元素来顶替堆顶，是因为堆要求完全二叉树结构，只有最后一个元素被拿走后，剩余节点仍然能保持完全二叉树的样子。
上浮和下沉这两个动作，是所有堆操作的发动机。无论是最小堆、最大堆，还是后面会说的优先队列、堆排序，本质上都是在围绕这两个动作做文章。
2.4 堆排序复杂度低，但实际排序为什么不常用它
堆排序是一个基于大顶堆的排序方法：先把数组构建成一个大顶堆，然后把堆顶元素和末尾元素交换，再把剩下的n-1个元素重新调整成大顶堆。重复这个过程，数组末尾就会逐步累积有序序列。
堆排序的时间复杂度稳定在O(n log n)，空间复杂度是O(1)，看上去很美。但实际开发中，主流语言内置的排序函数几乎都不会直接使用堆排序，而是选快速排序的改进版（比如C++的introsort，先快排，递归过深再转堆排序）。原因有两个：
第一，堆排序是不稳定排序。因为堆排序会在交换过程中把相同元素的相对顺序打乱，而很多业务场景需要保持稳定性排序。第二，堆排序的缓存局部性很差。它访问数组下标时是“跳跃式”的，比如访问下标2、4、8……，而快速排序是顺序分区扫描，CPU缓存命中率更高。实际跑起来，快排往往比堆排序快。
所以堆排序的重点不在“自己写一个排序”，而在于理解“怎么原地建堆”“怎么反复取最大元素”的思想。后续的优先队列、定时器、Dijkstra算法加速，都依赖这套取堆顶的能力。
2.5 视野打开：不只是二叉堆
二叉堆是最常见的堆，但不是唯一的堆。比如“D叉堆”让每个节点有多个孩子，降低树高，但增大了每个节点找最值孩子时的比较次数；又比如“配对堆”在并查集和图算法中能支持更高效地合并两个堆；“斐波那契堆”则把某些操作的均摊复杂度降到了O(1)。
新手不用急着把非二叉堆都学会，但可以知道一个事实：面试和工作中用到最多的还是二叉堆，因为它简单、可靠、内存占用低。像多路归并排序里用到的k路归并堆，本质上就是一个小顶堆，帮你从k个有序链表中每次取最小的头节点。这些应用只要能把二叉堆吃透，后面都很顺。
3. 运行时内存的堆：栈和堆的博弈
3.1 栈负责执行，堆负责生存
算法题讲完了，再说说程序真正运行时的内存布局。现代操作系统加载一个进程后，会为它分配一块虚拟地址空间，从低地址到高地址大致包含：代码段、数据段、堆区、内存映射区、栈区。这里的堆区，就是malloc、new或JVM堆对象分配内存的地方。
栈（Stack）和堆（Heap）最大的区别在于管理方式。栈由编译器自动管理，每次函数调用会创建栈帧，局部变量、函数参数、返回地址都放在栈帧里，函数返回时栈帧自动销毁。堆则没有这种“自动按作用域销毁”的机制，在C/C++里需要手动free/delete，不及时释放就会内存泄漏；在Java、Go这类带GC的语言里，虽然由垃圾收集器回收，但回收时机并不完全可控。
打个比方：栈很像厨房的操作台，你从一个菜做到下一个菜，上一个菜用完的盘子会自动被收走，速度快、空间相对固定；堆则像一个大型仓库，你可以随手去仓库里领一块区域存放需要长期保留的东西，但必须定期自己清理，或者依赖专业的仓库管理员（GC）来帮你清理。栈空间在大多数系统中只有几MB到十几MB，而堆空间却可以设置到几个GB甚至更多。
3.2 动手看地址：栈在高处，堆在低处
光背概念很难有直观感受，我建议你在自己的Linux环境跑下面这段C代码：
#include <stdio.h> #include <stdlib.h> int main() { int stack_var = 42; int *heap_var = (int *)malloc(sizeof(int)); *heap_var = 42; printf("stack addr: %p\n", (void *)&stack_var); printf("heap addr: %p\n", (void *)heap_var); free(heap_var); return 0; }我在一台常见的x86-64 Linux机器上得到的输出大致是：
stack addr: 0x7ffc9d3d4a2c heap addr: 0x55b03b8652a0可以看到栈变量地址明显比堆变量地址高很多。原因是进程的栈区位于虚拟地址空间的高地址区域，并且栈是向下增长的；堆区则在相对低的位置，向高地址方向增长。栈和堆看上去是“面对面生长”，这也是“栈溢出会把栈空间耗尽”这类问题出现的原因。
很多做Java开发的朋友可能没写过C语言，没关系，你也可以用JVM参数打印进程地址，效果类似。理解这块还方便你想通另一个问题：为什么栈分配快、堆分配慢？因为栈分配只需要移动栈指针，一条指令就完成了；而堆分配需要分配器去寻找合适的空闲内存块，还要处理并发加锁，自然慢很多。
3.3 堆外内存：被绕开的“堆”
Java程序员一定见过堆外内存这个词，尤其在Netty、Kafka这类高性能框架的相关文章里。它指的是JVM堆之外的内存，最典型的是java.nio.DirectByteBuffer分配的“直接内存”。
JVM在向操作系统发起读写操作时，底层会调用native的IO函数。如果数据放在Java堆内，那么native IO往往不能直接访问Java堆内存的地址，需要把数据先拷贝到一块操作系统能直接操作的内存中；而如果你用的是堆外的DirectByteBuffer，数据本身就在堆外，IO可以直接拿这块地址读写，少了一次内存拷贝。
于是就有了一个面试高频题：为什么Netty要使用堆外内存？答案就是减少拷贝，提高IO性能。堆外内存不受JVM的-Xmx限制，但受本机物理内存以及参数-XX:MaxDirectMemorySize限制；在未显式设置时，MaxDirectMemorySize默认与-Xmx一样大。管理不当就会出现“Direct buffer memory”的OutOfMemoryError，而且这种OOM还不一定被GC日志里的堆信息体现出来，排查起来比较迷。
我见过不少线上事故，都是因为只知道把-Xmx调大，却忘记了Netty直接内存的用量暴涨。定位时可以通过jcmd pid VM.native_memory summary来查看内存分布，也可以在JVM参数里加-XX:MaxDirectMemorySize给一个明确上限。堆外内存的性能优势让它不可不用，但它绝不意味着“可以无限申请”，手动释放和池化（如Netty的PooledByteBufAllocator）是一定要做好的。
3.4 堆空间不足，是不是只能加内存
不管是C++的malloc失败、Python的MemoryError，还是Java的java.lang.OutOfMemoryError，遇到堆空间不足，大多数人的第一反应是加内存条或调大堆上限。这个方向不能说全错，但很多时候并不会真正解决问题。
遇到堆空间不足，先分清两种情况：一种是程序当前真的需要很大的内存，而且业务是有意义的，比如加载大模型、处理超大图片，这时扩容是合理的；另一种是程序存在内存泄漏，或者对象被无意识持有了，比如把每次请求的临时数据都塞进了一个静态List，导致堆被慢慢填满，这时盲目扩容只是推迟崩溃时间，甚至会让full GC更加频繁。
排查Java堆问题的常规路径是：先看GC日志，确认OOM前是不是频繁Full GC、堆内存是否一直无法回收；再用jmap -dump:format=b,file=heap.bin <pid>导一份堆快照，用MAT等分析工具看Dominator Tree，找出哪些对象占据了最多内存，再顺着引用链找到谁在持有这些对象。排查Python内存问题也可以用tracemalloc：
import tracemalloc tracemalloc.start() # 这里运行你想要监控的业务代码 snapshot = tracemalloc.take_snapshot() top_stats = snapshot.statistics('lineno') for stat in top_stats[:10]: print(stat)它会告诉你每一行代码累计分配了多少内存。通过对比几次快照，就能看出内存是在哪个模块里持续增长的。
4. 实战拆解：用Python实现堆和TopK
4.1 语言自带的堆：Python heapq的正确打开方式
Python把二叉堆放在heapq模块中，默认是小顶堆。这意味着堆顶元素永远是序列里最小的元素。常用的API如下：
import heapq nums = [3, 1, 4, 1, 5, 9, 2, 6] # 原地建堆，O(n) heapq.heapify(nums) # 入堆 heapq.heappush(nums, 0) # 出堆，每次弹出当前最小值 min_val = heapq.heappop(nums) # 先替换堆顶再入堆，相当于一步完成pop+push，常用于TopK heapq.heapreplace(nums, 10) # 一行拿到最大的3个数 print(heapq.nlargest(3, nums)) # 一行拿到最小的3个数 print(heapq.nsmallest(3, nums))如果要用大顶堆，Python没有直接内置，最常用的技巧是存相反数：入堆时存-x，出堆时取-x。由此得到的就是原本意义上的最大值。例如：
heap = [] for x in [3, 1, 4, 1, 5, 9]: heapq.heappush(heap, -x) max_val = -heapq.heappop(heap) print(max_val) # 9这里容易出错的地方是，出堆之后别忘了做一次符号翻转。我看到很多初学者写了半天，最后打印的是负数，然后满脸疑惑地来问“为什么我的最大值是-9”。
4.2 手写一个最小堆，面试不再心虚
虽然实际开发中直接调heapq就行，但面试手写堆的题目仍然常见，特别是考察插入、删除和建堆。写一个简单的最小堆类会让你对堆的理解上一个台阶。
class MinHeap: def __init__(self): self.heap = [] def push(self, val): self.heap.append(val) self._sift_up(len(self.heap) - 1) def pop(self): if not self.heap: return None top = self.heap[0] last = self.heap.pop() if self.heap: self.heap[0] = last self._sift_down(0) return top def _sift_up(self, idx): parent = (idx - 1) // 2 while idx > 0 and self.heap[idx] < self.heap[parent]: self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx] idx = parent parent = (idx - 1) // 2 def _sift_down(self, idx): n = len(self.heap) while True: left = 2 * idx + 1 right = 2 * idx + 2 smallest = idx if left < n and self.heap[left] < self.heap[smallest]: smallest = left if right < n and self.heap[right] < self.heap[smallest]: smallest = right if smallest == idx: break self.heap[idx], self.heap[smallest] = self.heap[smallest], self.heap[idx] idx = smallest这个类里最值得研究的是sift_down。每次需要比较左孩子和右孩子，找出更小的那一个然后交换。如果忽略了其中一侧越界条件，代码会在访问self.heap[right]等位置时抛IndexError。此外，在pop方法里把最后一个元素移到堆顶再下沉，这是保持完全二叉树结构的关键技巧，不要图省事直接把两个孩子中较小的那个顶上根节点，那样数组里会出现空洞，堆的结构就错了。
4.3 自定义优先队列：不要让“不可比较”背锅
很多时候要放进堆里的不是整数，而是一个任务对象，需要按某个字段排序。直接使用heapq时，堆内部要比较两个元素的大小。如果对象没有实现比较方法，Python会抛TypeError：'<' not supported between instances of 'Task' and 'Task'。
解法之一是给类实现__lt__方法，告诉堆“先后顺序如何比较”。例如：
class Task: def __init__(self, priority, name): self.priority = priority self.name = name def __lt__(self, other): return self.priority < other.priority更常见的做法是往堆里插入(priority, counter, task)三元组。注意不要只插入(priority, task)，因为当两个任务优先级相同时，Python会继续比较第二个元素task，如果task对象不比大小，又会报错。加一个自增的counter可以保证所有优先级相同的情况下，按照入堆先后排序，同时不会触发task之间的比较。
这种处理方式在Java里也有对应版本，Java的PriorityQueue需要传入Comparator，否则要求元素实现Comparable。定义一个比较器时，同样要注意优先级相同的情况，否则两个优先级一致的任务会导致队列内部比较分不出胜负，虽然不一定报错，但顺序会不符合预期。
4.4 大数据量场景下的TopK：堆的经典主场
假设你有一个大文件，里面每一行是一个字符串，需要找出出现次数最多的前100个字符串。如果文件不大，你可以用Counter统计完直接排序，但如果是几十GB的日志，把所有统计结果排序不仅慢，而且没必要。这时堆就能派上用场。
思路是：先用哈希表统计每个字符串出现的次数，然后维护一个大小为K的小顶堆，遍历哈希表的过程中：
- 如果堆中元素不足K个，直接入堆；
- 如果当前字符串次数大于堆顶元素的次数，把堆顶替换掉。
为什么找最大K个要用小顶堆而不是大顶堆？因为小顶堆的堆顶是当前“前K大”里的最小值，一旦来了更大的数就可以马上淘汰掉最小值；如果用大顶堆，堆顶是当前前K大中的最大值，新元素永远比不过堆顶，就没有任何元素能被淘汰，堆里存的反而是所有元素里最小的K个，思路正好反了。
示例代码：
import heapq def top_k_frequent(words, k): # 这里省略 words 的统计逻辑，假设 counts 是 dict counts = {} for word in words: counts[word] = counts.get(word, 0) + 1 heap = [] for word, cnt in counts.items(): if len(heap) < k: heapq.heappush(heap, (cnt, word)) elif cnt > heap[0][0]: heapq.heapreplace(heap, (cnt, word)) # 堆顶在前，需要逆序得到从大到小 result = [] while heap: result.append(heapq.heappop(heap)[1]) result.reverse() return result最终内存占用只和K有关，在K远小于数据总量时，这是一个非常省内存的方案。实际在海量日志中统计Top IP、Top接口错误码，都可以把这个思路封装成一个通用函数，配合逐行读取大文件使用。
5. 避坑指南：常见误区和排查经验
5.1 关于堆的高频疑问速查表
| 疑问 | 答案 |
|---|---|
| 堆的插入/删除复杂度是多少 | O(log n)，其中n为堆中元素个数 |
| 建堆复杂度是多少 | O(n)，用从最后一个非叶子节点往前不断下沉的方法 |
| 堆排序是稳定排序吗 | 不是，堆排序在交换过程中会改变相同元素的相对顺序 |
| 找前K个最大元素用大顶堆还是小顶堆 | 用小顶堆，维持大小为K的堆，堆顶是前K个中的最小值 |
| Python heapq默认是什么堆 | 小顶堆，每次pop得到最小值；需要大顶堆时就存相反数 |
| C++ priority_queue默认是什么堆 | 大顶堆，需要传greater 来改成小顶堆 |
| Java的PriorityQueue默认是什么堆 | 小顶堆，可通过Comparator改成大顶堆 |
| 栈溢出一般是什么原因 | 无限递归、过大的局部变量、创建了过大的栈上数组 |
| Java堆报OutOfMemoryError怎么定位 | 看GC日志、导出堆快照用MAT分析，别盲目加-Xmx |
| 堆外内存报OOM怎么排查 | 检查MaxDirectMemorySize设置、用VM.native_memory查native内存占用 |
5.2 如何一眼判断是栈问题还是堆问题
在实践中，判断错误类型比盲目修复更重要。下面是几种常见报错信息和对应的排查方向：
- 如果你的C/C++程序崩溃并且日志里有“stack overflow”字样，说明大概率是栈溢出，先去看递归有没有退出条件，再看局部变量是否声明了一个巨大的数组。栈空间有限，一般只有几MB，把一个10MB的数组放在main函数里也会直接爆栈。
- Java出现StackOverflowError时同理，先往递归方向查；出现OutOfMemoryError: Java heap space的时候，才需要去调堆相关参数和找内存泄漏对象。
- Python里的RecursionError并不是全部因为递归过深，有时是递归函数忘记写终止条件，有时只是代码本来需要的递归深度超过了Python默认的递归限制。可以用sys.setrecursionlimit调高，但根因还是要改算法或增加退出条件。
- 如果你遇到的是“编译器堆空间不足”这类报错，先别怀疑你写的代码有问题。CC++编译器或JIT编译器在编译过程中自身也需要内存，当机器物理内存不足，或者并行编译任务开太多时，同样会报内存不够。降低优化级别、减少并行编译任务、关闭无关应用释放内存，是最常见的缓解方式。
5.3 一些“过来人”的体会和建议
最后分享几个我自己经历过的实际经验。有一段时间我在做日志分析工具，数据量大到直接用sort排完再取Top结果会占掉太多内存；换成堆以后，不管输入文件多大，进程内存都稳定在几十MB以内。这种“只保留最关心的K个，其余边来边丢”的思路，极其适合流式处理的场景，建议大家真正跑一遍。
还有一次，在线上的业务代码里看到有人为了取出数组中最大的10个数，先把整个数组排序再切片，完全没必要。对几千个数排序也许感知不到差异，但如果这个操作出现在高频接口路径里，一次排序可能是O(n log n)，而用堆只要O(n log k)。能明显降低CPU开销。算法题里刷过很多次堆，工作里却忘了用它，挺常见的。
我自己的学习方法向来是“两条腿走路”：数据结构堆靠算法题找手感，内存堆靠线上事故攒经验。两边都经历一遍后，你自然就会形成一套判断力——看到“堆”字，先反问一句，这里讨论的是执行逻辑里的优先队列，还是内存区域里的动态分配，还是IO层里的直接内存？这个能力比背再多概念都管用，建议你也试试。
