1. 两个堆的纠缠先分清概念再动手写码先问一个几乎所有人都会困惑的问题数据结构课上讲的那个堆和编译器报错里写的堆空间不足里的堆是一回事吗答案是否定的。内存管理里的堆是操作系统在进程虚拟地址空间中划分出的一块动态内存区域你用malloc或new申请内存时就是从那个堆里划空间。而数据结构里的堆是一个抽象的容器——一种能够快速取出最大元素或最小元素的树形结构。前者是内存布局的概念属于操作系统和编译器范畴后者是数据组织方式的概念属于算法和数据结构范畴。本文要讲的是后者。正是因为这两个堆刚好同名导致大量初学者在入门阶段就产生概念混淆后面一旦遇到heap corruption detected这类运行时报错就会怀疑是不是自己的堆写得有问题。先把概念厘清后面的学习会顺畅很多。数据结构里的堆到底是什么一句话概括堆是一棵完全二叉树并且满足堆序性质。所谓完全二叉树指的是除了最底层之外每一层节点都是满的且最底层的节点从左到右连续排列、没有空缺。堆序性质则分两种——大顶堆中每个父节点的值都大于等于它的子节点小顶堆中每个父节点的值都小于等于它的子节点。这带来的直接收益是堆顶就是全局最大元素或全局最小元素取值的时间复杂度是 O(1)。我第一次学到这里时其实有个很大的疑问为什么不直接用一个变量记录最大值因为堆还需要支持动态插入和动态删除——并且每做完一次操作都必须能在 O(log n) 时间内重新找到最大/最小值。如果你只用一个变量插入一个更大的元素当然可以更新它可一旦删除了这个最大元素你根本不知道第二大的在哪只能重新扫描一遍代价是 O(n)。堆的存在就是为了解决这个每次操作后都自动选出极值的问题。1.1 堆的存储方式为什么用数组而不是链表堆虽然是树形结构但它的实现几乎都用数组而不是像二叉树那样用节点指针。原因有三点完全二叉树天然适合用数组连续存储。按下标从 1 开始计算第i个节点的左孩子是2i右孩子是2i1父节点是i/2整数除法。下标从 0 开始的话左孩子是2i1右孩子是2i2父节点是(i-1)/2。我用 C 语言实现时习惯下标从 1 开始这样2i和i/2的写法更对称边界计算也少出错。数组的缓存局部性远优于链表。堆的操作总是沿着父到子或子到父的路径上下移动数组存储时这些节点大概率集中在相邻的内存区域CPU 缓存命中率更高。用链表存堆每次访问左右孩子都是一次指针跳转性能差距在大数据量下非常明显。不用处理指针释放问题代码简洁很多。这也是我实际写代码时感受最深的一点——堆结构本身不承担增删节点的内存管理职责它只维护一个数组的逻辑顺序需要扩容时realloc或重新分配即可不用担心树节点指针指来指去把自己绕晕。1.2 堆序性质的直观理解大顶堆和小顶堆选哪种取决于你要干什么。你需要快速拿最大值就用大顶堆需要快速拿最小值就用小顶堆。这里有个很容易误解的地方堆序性质只约束父节点和直接子节点的关系并不约束左子节点和右子节点之间的大小关系。也就是说大顶堆里左孩子的值完全可以大于右孩子的值整个堆也不是一个有序数组。堆只保证沿着从根到叶子的一条路径值依次递减大顶堆而同一层的节点之间没有任何顺序约定。所以堆的有序是一种比较弱的全局有序但恰恰是这个弱有序让插入和删除极值的操作都能在对数时间内完成。你要是强行把堆做成了完全有序比如整棵树的层序遍历都是有序的那插入一个元素的代价至少是 O(n)就失去了堆的意义。个人经验学堆的核心不要死记插入/删除的代码而是先把下沉和上浮这两个动作想明白。这两个动作是堆的所有操作的基石——你会在插入、删除、建堆、堆排序的每一个角落见到它们。2. 堆的基石下沉、上浮与建堆堆的所有动态操作本质上都是在维护一个被破坏的堆序性质。破坏发生在哪就用对应的修复动作把它补回来。这就是下沉sift down和上浮sift up的由来。2.1 上浮操作新元素插到末尾后往上爬往堆里插入元素的流程是这样的把新元素放到数组的末尾。这一步不会破坏完全二叉树的形状约束因为末尾就是下一层可插入的位置。新元素上来之后它的值可能比父节点更大大顶堆情况下堆序性质被破坏。把新元素和父节点比较如果违反了堆序就和父节点交换位置。因为交换之后新元素换到了父节点的位置它的新父节点又可能比它小继续往上比较直到满足堆序或到达根节点。这个从下往上不断交换的过程就是上浮。为什么叫浮因为违反堆序的元素像一个气泡一样一路向上冒直到抵达合适的位置。用一段伪代码描述void swim(arr, k): while k 1 且 arr[k/2] arr[k]: // 大顶堆父比子小则违反堆序 交换 arr[k/2] 和 arr[k] k k/2上浮操作的时间复杂度是 O(log n)因为从任意节点到根的最大路径长度就是树的高度而完全二叉树的高度是 log n 级别。2.2 下沉操作删除堆顶后往下滚删除堆顶元素是堆最独特的一个操作。为什么不能直接把第一个元素移除然后把后面的左移因为那会破坏完全二叉树的结构而且剩下的元素之间可能完全不满足堆序。标准做法是把堆顶元素数组第一个元素和数组最后一个元素交换。删除数组最后一个元素——现在它保存的是原来的堆顶可以直接 pop 掉。此时新的堆顶元素是从数组末尾搬上来的它的值大概率不够大大顶堆情况下往下看它可能比自己的孩子还小堆序被破坏。把它和两个孩子中较大的那个比较如果孩子的值更大就交换。交换之后它下移了一层但可能又比新的两个孩子小继续向下交换直到满足堆序或到达叶子。这个过程就是下沉。注意大顶堆下沉时要和两个孩子中较大的那个交换这是很多初学者容易写错的地方。如果随便交换了一个孩子即使新的堆顶比这个孩子大也可能比另一个孩子小整体堆序还是坏的。void sink(arr, k, n): while 2*k n: // 只要还有左孩子就继续 j 2*k // 假设较大的孩子是左孩子 if j n 且 arr[j] arr[j1]: // 如果右孩子存在且更大 j j1 // 更新为右孩子 if arr[k] arr[j]: // 父比最大的孩子还大堆序恢复 break 交换 arr[k] 和 arr[j] k j注意我加了参数n表示当前堆的有效大小。为什么需要这个参数因为后面堆排序时已经排好的后缀部分并不属于堆但还在数组里下沉必须知道堆的边界在哪里。2.3 建堆为什么从 n/2 开始向下调整初始化时如果给你一个无序数组怎么在 O(n) 时间内把它堆化这是很多人理解不到位的地方。直观的想法是从根到叶子对每个节点做一次下沉。但这会带来两个问题一是叶子节点没有孩子下沉无意义二是从根开始下沉根可能一路沉到很深的层但更底层的节点可能还乱着需要反复调整。正确的做法是从最后一个非叶子节点开始往前逐个做下沉。最后一个非叶子节点的下标是n/2下标从 1 算起因为它就是最后一个节点n的父节点。从n/2递减到 1依次执行下沉。为什么从底部开始调整我把这个过程类比成玩华容道如果你先把顶部的角色移到正确位置底部的角色可能又需要重新移动整个棋盘越调越乱。但如果你先处理底部——让每个局部子树先各自满足堆序——再往上合并时只需要把根节点下沉一层就可以让整个子树满足堆序。这个过程叫自底向上的堆化在每个节点上做一次下沉所有下沉操作的總工作量摊还下来是 O(n)而不是 O(n log n)。这里有个看似反直觉的结论建堆是 O(n) 的不是 O(n log n)。直觉上你会觉得n 个节点每个都下沉 log n 层应该是 O(n log n) 才对。但实际上绝大多数节点都在树的底部附近它们下沉的距离很短。真正精确计算后你会发现越靠近底层的节点数量越多、下沉距离越短总的工作量趋于线性。我当初为了验证这个结论写过一个简单测试用 100 万个随机数建堆统计实际的下沉交换次数结果确实接近 100 万级别而不是 2000 万级别。理论归理论亲手跑一遍数字对这个结论的信任感会完全不同。3. 手写一个二叉堆C 语言完整实现先声明一下我这里用的是 C 语言因为 C 的指针和内存管理暴露得最充分能把堆的每个细节都看清楚。如果你用的是 Pythonheapq模块封装得比较严实对理解堆的实现反而不太友好——但学完 C 版本之后用 Python 的heapq会非常轻松。3.1 结构定义与初始化我定义一个不固定容量的动态数组堆支持扩容。这里用到的技巧是初始化时预留一个额外空间下标 0 不用实际元素从下标 1 开始。#include stdio.h #include stdlib.h #include string.h typedef struct Heap { int *data; // 底层数组下标从 1 开始 int size; // 当前元素个数 int capacity; // 数组容量 int is_max; // 1 表示大顶堆0 表示小顶堆 } Heap; Heap* heap_create(int init_capacity, int is_max) { Heap *h (Heap*)malloc(sizeof(Heap)); h-capacity init_capacity; h-data (int*)malloc(sizeof(int) * (h-capacity 1)); // 多分配一个下标 0 不用 h-size 0; h-is_max is_max; return h; }is_max这个标志位是我做的小扩展同一个结构体同时支持大顶堆和小顶堆。后面比较时写一个内部函数处理避免在插入和删除代码里写两遍几乎一样的逻辑。扩容的逻辑和动态数组一样容量翻倍static void heap_resize(Heap *h) { if (h-size h-capacity) return; h-capacity * 2; h-data (int*)realloc(h-data, sizeof(int) * (h-capacity 1)); if (!h-data) { fprintf(stderr, realloc failed\n); exit(1); } }3.2 对元素进行比较统一大顶堆和小顶堆的差异比较函数是体现大顶堆/小顶堆差异的核心。如果用 C 的qsort风格写比较器会让代码更通用但初学者容易看不懂。我直接写一个内部辅助函数// 返回 1 表示 a 应该排在 b 的前面即 a 比 b 更优先 static int higher(Heap *h, int a, int b) { if (h-is_max) { return a b; } else { return a b; } }上浮和下沉里所有该不该交换的判断都收敛到这一个函数上。这样如果以后想改成结构体堆比如按结构体某个字段排序只需要改这一处。3.3 核心操作插入、删除堆顶、取堆顶上浮操作的实现// 上浮下标 k 的元素向上移动直到满足堆序 static void swim(Heap *h, int k) { while (k 1 higher(h, h-data[k], h-data[k / 2])) { int tmp h-data[k]; h-data[k] h-data[k / 2]; h-data[k / 2] tmp; k k / 2; } }下沉操作的实现// 下沉下标 k 的元素向下移动直到满足堆序n 是当前堆大小 static void sink(Heap *h, int k, int n) { while (2 * k n) { int j 2 * k; // 选择两个孩子中更优先的那个 if (j n higher(h, h-data[j 1], h-data[j])) { j j 1; } // 如果当前节点已经比最优先的孩子还优先堆序恢复 if (!higher(h, h-data[j], h-data[k])) { break; } int tmp h-data[k]; h-data[k] h-data[j]; h-data[j] tmp; k j; } }注意这里下沉比之前伪代码多了一个判断维度higher(h, h-data[j1], h-data[j])是选择更优先的孩子然后如果当前节点已经比这个最优先的孩子还优先!higher(...)就停。这个逻辑同时兼容大顶堆和小顶堆代码可读性也还不错。插入和删除的实现void heap_push(Heap *h, int val) { heap_resize(h); h-size; h-data[h-size] val; swim(h, h-size); } int heap_pop(Heap *h) { if (h-size 0) { fprintf(stderr, heap is empty\n); exit(1); } int top h-data[1]; h-data[1] h-data[h-size]; h-size--; sink(h, 1, h-size); return top; } int heap_top(Heap *h) { if (h-size 0) { fprintf(stderr, heap is empty\n); exit(1); } return h-data[1]; } int heap_empty(Heap *h) { return h-size 0; }3.4 建堆从数组直接堆化// 用数组 a[0..n-1] 原地建堆直接填到堆的内部数组中 void heap_build_from_array(Heap *h, int *a, int n) { // 确保容量够 while (h-capacity n) { h-capacity * 2; } h-data (int*)realloc(h-data, sizeof(int) * (h-capacity 1)); memcpy(h-data 1, a, sizeof(int) * n); h-size n; // 从最后一个非叶子节点开始逐个下沉 for (int i n / 2; i 1; i--) { sink(h, i, n); } }这个建堆的实现和我前文的描述一致从n/2往前逐个下沉。测试的时候可以打印堆的数组内容验证每个父节点都比孩子更优先。我建议你写一个简单的print_heap函数把数组按层打印出来然后自己构造几组数据检查。比如数组[1, 3, 5, 7, 9, 2, 4, 6, 8]建堆后的层序遍历结果和原始数组对比能非常直观地看出实际排序顺序和堆序的差别。这里有一个我踩过多次的坑下标从 1 开始但用户传入的数组下标从 0 开始memcpy到h-data 1没问题但后续对原始数组a的任何操作都要注意偏置。我一度在写堆排序时把a[i]和h-data[i]混淆排查了很久才发现是下标偏置的问题。写注释时把这件事写明以后再看代码不会踩同样的坑。3.5 测试代码用随机数据验证正确性这一步非常关键你写完堆之后一定要做一次系统性测试不然很难确定实现是否正确。我的做法是随机生成一批数压入堆再不断 pop验证 pop 出来的序列是否有序大顶堆应该递减小顶堆应该递增。int main() { srand(2024); int n 100000; Heap *h heap_create(16, 1); // 大顶堆 // 随机插入 10 万个元素 for (int i 0; i n; i) { heap_push(h, rand() % 1000000); } // 逐个弹出验证是否递减 int prev heap_pop(h); for (int i 1; i n; i) { int cur heap_pop(h); if (cur prev) { printf(ERROR: heap property violated at %d\n, i); return 1; } prev cur; } printf(All %d elements popped in correct order\n, n); heap_free(h); return 0; }第一次跑这个测试时我的实现还真暴露了问题——原因是sink里j n的判断写成了j h-size。在堆排序场景中n当前堆有效大小和h-size可能是不同的因为堆排序要把已排序的后缀部分排除在堆外。这个 bug 在只做插入删除的场景里不会出现一上堆排序就暴露。所以我强烈建议把n作为参数显式传入sink而不要依赖结构体里的size。4. 堆的实战堆排序和 TopK堆学完之后如果不用很快会忘。这一节讲两个最经典的应用场景堆排序和 TopK 问题。4.1 堆排序原地排序的完整流程堆排序是堆最著名的应用。它的思路朴素到近乎粗暴既然大顶堆的堆顶是最大值那把最大值挪到数组末尾再对剩下的部分重新调整堆再取堆顶……不断重复数组的末尾就会逐渐形成一个从大到小排列的后缀最终整个数组有序。具体步骤将无序数组原地建堆大顶堆。把堆顶元素最大值和当前堆的最后一个元素交换。这时最大值到了数组末尾堆的有效大小减 1。对新的堆顶做一次下沉恢复堆序。重复步骤 2 和 3直到堆的有效大小变为 1。此时数组已经按升序排列。为什么大顶堆排出来是升序而不是降序因为最大值被扔到数组末尾末尾是数组的高下标区域不断把最大值放到高下标区最终高下标区存放的是从大到小的序列整体就是升序。C 语言实现void heap_sort(int *a, int n) { // 1. 原地建大顶堆 // 这里不用调用 Heap 结构体直接对数组操作 // 建堆从最后一个非叶子节点 n/2 - 1 开始下标从 0 开始的版本 // 为了统一下面使用下标从 0 开始的版本演示 // 建堆 for (int i n / 2 - 1; i 0; i--) { // 下沉sift_down(a, i, n) int k i; while (2 * k 1 n) { int j 2 * k 1; if (j 1 n a[j 1] a[j]) { j j 1; } if (a[k] a[j]) break; int tmp a[k]; a[k] a[j]; a[j] tmp; k j; } } // 2. 不断把堆顶交换到末尾 for (int len n - 1; len 0; len--) { int tmp a[0]; a[0] a[len]; a[len] tmp; // 对 a[0] 做下沉堆的大小是 len int k 0; while (2 * k 1 len) { int j 2 * k 1; if (j 1 len a[j 1] a[j]) { j j 1; } if (a[k] a[j]) break; int tmp2 a[k]; a[k] a[j]; a[j] tmp2; k j; } } }这段代码没有复用之前的Heap结构体直接在数组上操作。这样做的理由是堆排序是原地排序不需要额外的动态内存用结构体反而多一层封装。实际工程里这两种写法都有我觉得初学最好把两种都写一遍——带结构体的版本练习堆的操作本身的正确性直接对数组操作的版本练习原位调整的细节。堆排序的时间复杂度是稳定的 O(n log n)建堆 O(n)n-1 次下沉每轮 O(log n)合计 O(n log n)。空间复杂度 O(1)。它和快速排序相比最显著的特征是时间复杂度与数据初始分布无关无论数据是有序的还是乱序的它都是那么稳定不会出现快排那种 O(n²) 的退化场景。代价是内部循环操作较多常数因子比快排大在大多数硬件实测中通常比快排慢一点。4.2 TopK 问题海量数据里找最大/最小的 K 个这里有个非常经典也极具迷惑性的问题找数组中最大的 K 个数用大顶堆还是小顶堆很多人第一反应是要最大的 K 个数当然用大顶堆每次把最大的顶上去。但这是错的。正确做法是维护一个大小为 K 的小顶堆遍历数组时如果当前元素比堆顶大就替换堆顶并下沉遍历结束后堆里的 K 个元素就是最大的 K 个数。为什么用小顶堆因为小顶堆的堆顶是堆里最小的元素也就是当前最大的 K 个数中最小的那个——也就是 K 个最大数的门槛。新元素只有比这个门槛大才有资格进入前 K。每次淘汰门槛堆中新加入的元素就是当前数组里更大的候选者。用小顶堆我们始终能知道当前最小的门槛是谁从而决定要不要把它换掉。如果用大顶堆堆顶是最大数新元素来了你没法判断它能不能进前 K——你必须要和 K 个最大的数中最小的那个比而大顶堆给不了你这个信息。复杂度方面遍历 n 个元素每个元素最坏情况触发一次 O(log K) 的下沉总复杂度 O(n log K)空间 O(K)。在 K 远小于 n 的场景比如从 10 亿数据里找前 100非常划算。这段代码可以直接用前文的Heap结构体按小顶堆初始化然后写一个循环替换void find_topk(int *a, int n, int k, int *result) { Heap *h heap_create(k, 0); // 小顶堆 for (int i 0; i n; i) { if (h-size k) { heap_push(h, a[i]); } else if (a[i] heap_top(h)) { heap_pop(h); heap_push(h, a[i]); } } // result 数组保存堆里的 k 个元素需要的话再排个序 for (int i 0; i k; i) { result[i] h-data[i 1]; } heap_free(h); }注意result里保存的元素顺序不是有序的就是堆的无序存储顺序。如果要按从大到小输出可以先 pop 全部元素构造一个有序序列或者额外做一个排序。别漏掉这个细节我见过不少人拿堆内部数组的顺序直接当作答案输出结果发现顺序不对。4.3 动态数据流的中位数两个堆配合的进阶玩法TopK 已经算是常见应用了但堆还有一个非常漂亮的技巧——用一个大顶堆和小顶堆配合在动态数据流中维护中位数。思路是维护两个堆大顶堆保存较小的一半数小顶堆保存较大的一半数并且保证大顶堆的大小要么等于小顶堆要么比小顶堆多一个。这样中位数就是大顶堆的堆顶奇数个数时或者大顶堆和小顶堆堆顶的平均值偶数个数时。插入新元素时先和大顶堆堆顶比较决定进哪个堆然后通过堆之间的元素移动来维持两个堆的大小平衡。整个过程每个元素进堆 O(log n)取中位数 O(1)。这里有个关键细节两个堆的大小差不能超过 1。如果大顶堆比小顶堆多 2 个以上就把大顶堆堆顶弹出压入小顶堆反过来也一样。移动后两个堆的内部结构都会被自动调整因为它们本身就是堆。这个场景在实时统计、在线排行榜等场景中很常见。我最早在做一个股票价格模拟系统时用过这个思路——数据以流的形式不断到达需要随时知道当前价格的中位数。如果用排序数组做每次插入都是 O(n)用两个堆做每个操作都是 O(log n)实测百万级数据量时差距接近几个数量级。5. 堆和栈、堆内存的辨析面试和实战中的高频误区这一节我专门写给即将面试或正在做期末复习的读者。作为一个经常当面试官的人我可以告诉你堆和栈有什么区别这个问题十个候选人里至少有三个会把数据结构的堆和内存的堆搅在一起。下面把这些概念一次性理清。5.1 数据结构角度堆 vs 栈数据结构层面栈是一种 LIFO后进先出的线性结构操作受限——只能在栈顶压入和弹出。堆是一种树形结构支持 O(log n) 插入和 O(log n) 删除极值。两者唯一的共同点是都叫堆/栈以及都是容器其余没有任何直接关系。面试时一旦被问到堆和栈的区别你应该先反问一句您问的是数据结构层面还是内存分布层面这样既展示了你概念的清晰度也把问题引向更明确的讨论方向。数据结构栈最常见的应用是函数调用栈、括号匹配、表达式求值堆最常见的应用是优先队列、调度算法、堆排序。5.2 内存角度堆区 vs 栈区内存分布层面程序运行时栈区和堆区是进程虚拟地址空间中两个不同的区域栈区由编译器自动分配和释放存放局部变量、函数参数、返回地址等。它的分配和释放效率极高只需要移动栈顶指针但空间有限递归过深或声明过大的局部数组就会栈溢出。堆区由程序员手动申请和释放存放动态分配的内存。空间更大、更灵活但需要手动管理生命周期否则就是内存泄漏。malloc/new分配的内存就在堆区。运行时报错 stack overflow 基本就是栈空间不够用heap 空间不足则是堆区内存耗尽。前者最常见的原因是递归无终止条件或局部数组太大后者最常见的原因是大量内存申请后没有释放累积导致堆空间枯竭。5.3 常见误区清单下面我把这些年见过的错误说法整理成一个清单每条后面给出正确解释误区正确理解堆就是malloc的那块内存malloc分配的内存确实来自堆区但堆首先是数据结构术语两者命名撞车栈比堆快从内存分配/释放机制看栈确实比堆快自动管理 vs 手动管理但这是内存层面的结论与数据结构无关大顶堆就是最大值堆对但堆里不是所有元素都有序堆顶才是极值堆排序一定比快排快错堆排序时间复杂度稳定但常数因子更大多数实测慢于快排TopK 最大 K 个用大顶堆错用小顶堆维护门槛才是正确选择这些误区之所以普遍本质上还是因为堆这个词被两个不同领域复用了。你只要记住讨论数据结构时堆完全二叉树堆序性质讨论内存时堆动态内存区域。分清这一点后面很多困惑都会消失。5.4 面试题里堆的难度梯度如果是校招/实习生级别最常见的是实现堆排序、用堆求 TopK、手写优先队列。社招的话更侧重场景设计比如如何在海量日志中找到出现频率最高的前一百个词——本质上还是 TopK但要先做词频统计再进堆。再高级一点会问求实时数据流的中位数就用到两个堆配合的技巧。我个人的建议是面试前除了把插入删除和堆排序写熟一定要能讲清楚为什么建堆是 O(n)以及为什么 TopK 要用小顶堆这两个推导过程。面试官问堆大概率就是看你能不能讲清楚这两个为什么。光会写代码而说不清原理的候选人在我这里最多拿一半分。6. 写堆代码的调试经验与性能优化细节最后这部分全是实操层面的经验。堆的实现代码不长但它有两个特点一是边界条件多二是状态隐含在数组里肉眼不容易发现问题。基于我实际调试的经历分享几个最有价值的判断方法和优化思路。6.1 堆代码最常见的三类 bug 及排查方法边界条件类 bug。最典型的是左孩子是否存在的判断写错。下标从 1 开始左孩子是2k但2k可能超过堆大小n此时当前节点是叶子下沉应该终止。我把这个条件写错过几次表现出来就是小数据测试正常数据量一大就出现堆顶不是极值的错误。排查方法是构造边界数据插入一个元素、插入两个、三个……手动走一遍代码比随机数据更容易暴露边界问题。下标混淆类 bug。前面提到过sink(h, 1, h-size)里的第三个参数到底是堆大小还是数组容量是重灾区。堆排序时尤其容易混——因为排序过程中堆的有效大小和数组长度是两个概念。我的习惯是函数签名里凡是用到长度的参数一律取名为n和count不用size因为在Heap结构体里size已经隐含了当前堆大小的意思函数参数再用它会增加迷惑性。结构体生命周期类 bug。realloc之后没有更新capacity、heap_free后没有置空指针、扩容时忘记多分配一个空间下标 0 不用。这类 bug 通常在压力测试下才暴露。我的建议是在heap_resize里加入容量检查如果size快接近capacity就提前扩容不要等到插入时才想起来检查。这类防御式编程能帮你减少大量无谓的排查时间。6.2 复杂度分析与优化方向堆的各项操作复杂度需要烂熟于心操作时间复杂度取堆顶O(1)插入O(log n)删除堆顶O(log n)建堆O(n)堆排序O(n log n)优化方向上有一个不太多人注意的点如果堆的底层数组频繁插入删除导致频繁realloc性能损耗很明显。我的做法是在初始化时根据数据量预估一个初始容量比如预计处理 10 万数据就heap_create(100000, 1)后面基本不需要扩容。如果实在无法预估扩容策略用翻倍而不是每次加固定大小这样摊还复杂度是 O(1)。还有一个优化叫做索引堆Index Heap适合处理需要更新堆中某个已有元素的优先级的场景。普通堆一旦元素入堆后你不知道它在数组的哪个位置无法直接修改它。索引堆额外维护一个位置数组记录每个元素的索引从而支持 O(log n) 的修改操作。这个在 Dijkstra 最短路径算法的堆优化版本里非常关键。如果你已经能熟练写出普通堆可以去研究一下索引堆的改进思路——它能帮你对堆的本质是下标映射有更深的理解。6.3 什么时候不该用堆这是一个容易被忽略但同样重要的问题。堆不是万能的以下场景你应该考虑其他数据结构需要按任意顺序遍历所有元素。堆只保证堆顶是极值遍历时如果你想输出有序序列需要不断 pop得到的是有序序列但内部数组本身并不是完全有序的。此时直接用排序数组更合适。需要快速查找某个具体值是否存在。堆的查找是 O(n) 的没有任何索引可以利用。这种场景应该用哈希表或平衡树。数据量极小几十个元素。线性扫描找出最大值的开销远小于建堆加维护堆序的开销。堆的 O(log n) 优势只在 n 足够大时才能抵消常数因子。判断该不该用堆本质上是一个操作频率问题你的场景是否高频执行插入取极值如果是堆是你的首选如果不是排序或线性扫描可能更简单也更划算。6.4 从手写堆到标准库的过渡一旦通过手写堆理解了底层原理日常开发中强烈推荐直接用语言的标准库——C 的std::priority_queue、Python 的heapq、Java 的PriorityQueue这些实现经过生产环境千万级验证边界条件处理得远比你自己写的健壮。但这里有个自我检验的建议你在标准库里要能看懂入参含义是什么、比较器怎么定义、默认是大顶堆还是小顶堆。以 C 为例std::priority_queueT默认是大顶堆靠的是lessT比较器如果你要小顶堆就要传入greaterT。很多人在这一步不知所措——因为他们只记得调库不知道堆的语义跟less/greater的关系。理解了本文中的higher函数之后再看标准库比较器就豁然开朗了底层逻辑完全一样标准库只是把这个函数抽象成了模板参数。我自己玩堆的最大收获其实是看任何数据结构先找它的不变量——堆的不变量就是堆序性质所有操作的维护都在保护这个不变量。一旦抓住这个核心后面学跳表、B 树、红黑树思路都会非常清晰。数据结构之间的差异说到底就是不变量不同、维护手段不同、操作代价不同而已。 数据结构堆详解：从二叉堆实现到堆排序与TopK应用
1. 两个堆的纠缠先分清概念再动手写码先问一个几乎所有人都会困惑的问题数据结构课上讲的那个堆和编译器报错里写的堆空间不足里的堆是一回事吗答案是否定的。内存管理里的堆是操作系统在进程虚拟地址空间中划分出的一块动态内存区域你用malloc或new申请内存时就是从那个堆里划空间。而数据结构里的堆是一个抽象的容器——一种能够快速取出最大元素或最小元素的树形结构。前者是内存布局的概念属于操作系统和编译器范畴后者是数据组织方式的概念属于算法和数据结构范畴。本文要讲的是后者。正是因为这两个堆刚好同名导致大量初学者在入门阶段就产生概念混淆后面一旦遇到heap corruption detected这类运行时报错就会怀疑是不是自己的堆写得有问题。先把概念厘清后面的学习会顺畅很多。数据结构里的堆到底是什么一句话概括堆是一棵完全二叉树并且满足堆序性质。所谓完全二叉树指的是除了最底层之外每一层节点都是满的且最底层的节点从左到右连续排列、没有空缺。堆序性质则分两种——大顶堆中每个父节点的值都大于等于它的子节点小顶堆中每个父节点的值都小于等于它的子节点。这带来的直接收益是堆顶就是全局最大元素或全局最小元素取值的时间复杂度是 O(1)。我第一次学到这里时其实有个很大的疑问为什么不直接用一个变量记录最大值因为堆还需要支持动态插入和动态删除——并且每做完一次操作都必须能在 O(log n) 时间内重新找到最大/最小值。如果你只用一个变量插入一个更大的元素当然可以更新它可一旦删除了这个最大元素你根本不知道第二大的在哪只能重新扫描一遍代价是 O(n)。堆的存在就是为了解决这个每次操作后都自动选出极值的问题。1.1 堆的存储方式为什么用数组而不是链表堆虽然是树形结构但它的实现几乎都用数组而不是像二叉树那样用节点指针。原因有三点完全二叉树天然适合用数组连续存储。按下标从 1 开始计算第i个节点的左孩子是2i右孩子是2i1父节点是i/2整数除法。下标从 0 开始的话左孩子是2i1右孩子是2i2父节点是(i-1)/2。我用 C 语言实现时习惯下标从 1 开始这样2i和i/2的写法更对称边界计算也少出错。数组的缓存局部性远优于链表。堆的操作总是沿着父到子或子到父的路径上下移动数组存储时这些节点大概率集中在相邻的内存区域CPU 缓存命中率更高。用链表存堆每次访问左右孩子都是一次指针跳转性能差距在大数据量下非常明显。不用处理指针释放问题代码简洁很多。这也是我实际写代码时感受最深的一点——堆结构本身不承担增删节点的内存管理职责它只维护一个数组的逻辑顺序需要扩容时realloc或重新分配即可不用担心树节点指针指来指去把自己绕晕。1.2 堆序性质的直观理解大顶堆和小顶堆选哪种取决于你要干什么。你需要快速拿最大值就用大顶堆需要快速拿最小值就用小顶堆。这里有个很容易误解的地方堆序性质只约束父节点和直接子节点的关系并不约束左子节点和右子节点之间的大小关系。也就是说大顶堆里左孩子的值完全可以大于右孩子的值整个堆也不是一个有序数组。堆只保证沿着从根到叶子的一条路径值依次递减大顶堆而同一层的节点之间没有任何顺序约定。所以堆的有序是一种比较弱的全局有序但恰恰是这个弱有序让插入和删除极值的操作都能在对数时间内完成。你要是强行把堆做成了完全有序比如整棵树的层序遍历都是有序的那插入一个元素的代价至少是 O(n)就失去了堆的意义。个人经验学堆的核心不要死记插入/删除的代码而是先把下沉和上浮这两个动作想明白。这两个动作是堆的所有操作的基石——你会在插入、删除、建堆、堆排序的每一个角落见到它们。2. 堆的基石下沉、上浮与建堆堆的所有动态操作本质上都是在维护一个被破坏的堆序性质。破坏发生在哪就用对应的修复动作把它补回来。这就是下沉sift down和上浮sift up的由来。2.1 上浮操作新元素插到末尾后往上爬往堆里插入元素的流程是这样的把新元素放到数组的末尾。这一步不会破坏完全二叉树的形状约束因为末尾就是下一层可插入的位置。新元素上来之后它的值可能比父节点更大大顶堆情况下堆序性质被破坏。把新元素和父节点比较如果违反了堆序就和父节点交换位置。因为交换之后新元素换到了父节点的位置它的新父节点又可能比它小继续往上比较直到满足堆序或到达根节点。这个从下往上不断交换的过程就是上浮。为什么叫浮因为违反堆序的元素像一个气泡一样一路向上冒直到抵达合适的位置。用一段伪代码描述void swim(arr, k): while k 1 且 arr[k/2] arr[k]: // 大顶堆父比子小则违反堆序 交换 arr[k/2] 和 arr[k] k k/2上浮操作的时间复杂度是 O(log n)因为从任意节点到根的最大路径长度就是树的高度而完全二叉树的高度是 log n 级别。2.2 下沉操作删除堆顶后往下滚删除堆顶元素是堆最独特的一个操作。为什么不能直接把第一个元素移除然后把后面的左移因为那会破坏完全二叉树的结构而且剩下的元素之间可能完全不满足堆序。标准做法是把堆顶元素数组第一个元素和数组最后一个元素交换。删除数组最后一个元素——现在它保存的是原来的堆顶可以直接 pop 掉。此时新的堆顶元素是从数组末尾搬上来的它的值大概率不够大大顶堆情况下往下看它可能比自己的孩子还小堆序被破坏。把它和两个孩子中较大的那个比较如果孩子的值更大就交换。交换之后它下移了一层但可能又比新的两个孩子小继续向下交换直到满足堆序或到达叶子。这个过程就是下沉。注意大顶堆下沉时要和两个孩子中较大的那个交换这是很多初学者容易写错的地方。如果随便交换了一个孩子即使新的堆顶比这个孩子大也可能比另一个孩子小整体堆序还是坏的。void sink(arr, k, n): while 2*k n: // 只要还有左孩子就继续 j 2*k // 假设较大的孩子是左孩子 if j n 且 arr[j] arr[j1]: // 如果右孩子存在且更大 j j1 // 更新为右孩子 if arr[k] arr[j]: // 父比最大的孩子还大堆序恢复 break 交换 arr[k] 和 arr[j] k j注意我加了参数n表示当前堆的有效大小。为什么需要这个参数因为后面堆排序时已经排好的后缀部分并不属于堆但还在数组里下沉必须知道堆的边界在哪里。2.3 建堆为什么从 n/2 开始向下调整初始化时如果给你一个无序数组怎么在 O(n) 时间内把它堆化这是很多人理解不到位的地方。直观的想法是从根到叶子对每个节点做一次下沉。但这会带来两个问题一是叶子节点没有孩子下沉无意义二是从根开始下沉根可能一路沉到很深的层但更底层的节点可能还乱着需要反复调整。正确的做法是从最后一个非叶子节点开始往前逐个做下沉。最后一个非叶子节点的下标是n/2下标从 1 算起因为它就是最后一个节点n的父节点。从n/2递减到 1依次执行下沉。为什么从底部开始调整我把这个过程类比成玩华容道如果你先把顶部的角色移到正确位置底部的角色可能又需要重新移动整个棋盘越调越乱。但如果你先处理底部——让每个局部子树先各自满足堆序——再往上合并时只需要把根节点下沉一层就可以让整个子树满足堆序。这个过程叫自底向上的堆化在每个节点上做一次下沉所有下沉操作的總工作量摊还下来是 O(n)而不是 O(n log n)。这里有个看似反直觉的结论建堆是 O(n) 的不是 O(n log n)。直觉上你会觉得n 个节点每个都下沉 log n 层应该是 O(n log n) 才对。但实际上绝大多数节点都在树的底部附近它们下沉的距离很短。真正精确计算后你会发现越靠近底层的节点数量越多、下沉距离越短总的工作量趋于线性。我当初为了验证这个结论写过一个简单测试用 100 万个随机数建堆统计实际的下沉交换次数结果确实接近 100 万级别而不是 2000 万级别。理论归理论亲手跑一遍数字对这个结论的信任感会完全不同。3. 手写一个二叉堆C 语言完整实现先声明一下我这里用的是 C 语言因为 C 的指针和内存管理暴露得最充分能把堆的每个细节都看清楚。如果你用的是 Pythonheapq模块封装得比较严实对理解堆的实现反而不太友好——但学完 C 版本之后用 Python 的heapq会非常轻松。3.1 结构定义与初始化我定义一个不固定容量的动态数组堆支持扩容。这里用到的技巧是初始化时预留一个额外空间下标 0 不用实际元素从下标 1 开始。#include stdio.h #include stdlib.h #include string.h typedef struct Heap { int *data; // 底层数组下标从 1 开始 int size; // 当前元素个数 int capacity; // 数组容量 int is_max; // 1 表示大顶堆0 表示小顶堆 } Heap; Heap* heap_create(int init_capacity, int is_max) { Heap *h (Heap*)malloc(sizeof(Heap)); h-capacity init_capacity; h-data (int*)malloc(sizeof(int) * (h-capacity 1)); // 多分配一个下标 0 不用 h-size 0; h-is_max is_max; return h; }is_max这个标志位是我做的小扩展同一个结构体同时支持大顶堆和小顶堆。后面比较时写一个内部函数处理避免在插入和删除代码里写两遍几乎一样的逻辑。扩容的逻辑和动态数组一样容量翻倍static void heap_resize(Heap *h) { if (h-size h-capacity) return; h-capacity * 2; h-data (int*)realloc(h-data, sizeof(int) * (h-capacity 1)); if (!h-data) { fprintf(stderr, realloc failed\n); exit(1); } }3.2 对元素进行比较统一大顶堆和小顶堆的差异比较函数是体现大顶堆/小顶堆差异的核心。如果用 C 的qsort风格写比较器会让代码更通用但初学者容易看不懂。我直接写一个内部辅助函数// 返回 1 表示 a 应该排在 b 的前面即 a 比 b 更优先 static int higher(Heap *h, int a, int b) { if (h-is_max) { return a b; } else { return a b; } }上浮和下沉里所有该不该交换的判断都收敛到这一个函数上。这样如果以后想改成结构体堆比如按结构体某个字段排序只需要改这一处。3.3 核心操作插入、删除堆顶、取堆顶上浮操作的实现// 上浮下标 k 的元素向上移动直到满足堆序 static void swim(Heap *h, int k) { while (k 1 higher(h, h-data[k], h-data[k / 2])) { int tmp h-data[k]; h-data[k] h-data[k / 2]; h-data[k / 2] tmp; k k / 2; } }下沉操作的实现// 下沉下标 k 的元素向下移动直到满足堆序n 是当前堆大小 static void sink(Heap *h, int k, int n) { while (2 * k n) { int j 2 * k; // 选择两个孩子中更优先的那个 if (j n higher(h, h-data[j 1], h-data[j])) { j j 1; } // 如果当前节点已经比最优先的孩子还优先堆序恢复 if (!higher(h, h-data[j], h-data[k])) { break; } int tmp h-data[k]; h-data[k] h-data[j]; h-data[j] tmp; k j; } }注意这里下沉比之前伪代码多了一个判断维度higher(h, h-data[j1], h-data[j])是选择更优先的孩子然后如果当前节点已经比这个最优先的孩子还优先!higher(...)就停。这个逻辑同时兼容大顶堆和小顶堆代码可读性也还不错。插入和删除的实现void heap_push(Heap *h, int val) { heap_resize(h); h-size; h-data[h-size] val; swim(h, h-size); } int heap_pop(Heap *h) { if (h-size 0) { fprintf(stderr, heap is empty\n); exit(1); } int top h-data[1]; h-data[1] h-data[h-size]; h-size--; sink(h, 1, h-size); return top; } int heap_top(Heap *h) { if (h-size 0) { fprintf(stderr, heap is empty\n); exit(1); } return h-data[1]; } int heap_empty(Heap *h) { return h-size 0; }3.4 建堆从数组直接堆化// 用数组 a[0..n-1] 原地建堆直接填到堆的内部数组中 void heap_build_from_array(Heap *h, int *a, int n) { // 确保容量够 while (h-capacity n) { h-capacity * 2; } h-data (int*)realloc(h-data, sizeof(int) * (h-capacity 1)); memcpy(h-data 1, a, sizeof(int) * n); h-size n; // 从最后一个非叶子节点开始逐个下沉 for (int i n / 2; i 1; i--) { sink(h, i, n); } }这个建堆的实现和我前文的描述一致从n/2往前逐个下沉。测试的时候可以打印堆的数组内容验证每个父节点都比孩子更优先。我建议你写一个简单的print_heap函数把数组按层打印出来然后自己构造几组数据检查。比如数组[1, 3, 5, 7, 9, 2, 4, 6, 8]建堆后的层序遍历结果和原始数组对比能非常直观地看出实际排序顺序和堆序的差别。这里有一个我踩过多次的坑下标从 1 开始但用户传入的数组下标从 0 开始memcpy到h-data 1没问题但后续对原始数组a的任何操作都要注意偏置。我一度在写堆排序时把a[i]和h-data[i]混淆排查了很久才发现是下标偏置的问题。写注释时把这件事写明以后再看代码不会踩同样的坑。3.5 测试代码用随机数据验证正确性这一步非常关键你写完堆之后一定要做一次系统性测试不然很难确定实现是否正确。我的做法是随机生成一批数压入堆再不断 pop验证 pop 出来的序列是否有序大顶堆应该递减小顶堆应该递增。int main() { srand(2024); int n 100000; Heap *h heap_create(16, 1); // 大顶堆 // 随机插入 10 万个元素 for (int i 0; i n; i) { heap_push(h, rand() % 1000000); } // 逐个弹出验证是否递减 int prev heap_pop(h); for (int i 1; i n; i) { int cur heap_pop(h); if (cur prev) { printf(ERROR: heap property violated at %d\n, i); return 1; } prev cur; } printf(All %d elements popped in correct order\n, n); heap_free(h); return 0; }第一次跑这个测试时我的实现还真暴露了问题——原因是sink里j n的判断写成了j h-size。在堆排序场景中n当前堆有效大小和h-size可能是不同的因为堆排序要把已排序的后缀部分排除在堆外。这个 bug 在只做插入删除的场景里不会出现一上堆排序就暴露。所以我强烈建议把n作为参数显式传入sink而不要依赖结构体里的size。4. 堆的实战堆排序和 TopK堆学完之后如果不用很快会忘。这一节讲两个最经典的应用场景堆排序和 TopK 问题。4.1 堆排序原地排序的完整流程堆排序是堆最著名的应用。它的思路朴素到近乎粗暴既然大顶堆的堆顶是最大值那把最大值挪到数组末尾再对剩下的部分重新调整堆再取堆顶……不断重复数组的末尾就会逐渐形成一个从大到小排列的后缀最终整个数组有序。具体步骤将无序数组原地建堆大顶堆。把堆顶元素最大值和当前堆的最后一个元素交换。这时最大值到了数组末尾堆的有效大小减 1。对新的堆顶做一次下沉恢复堆序。重复步骤 2 和 3直到堆的有效大小变为 1。此时数组已经按升序排列。为什么大顶堆排出来是升序而不是降序因为最大值被扔到数组末尾末尾是数组的高下标区域不断把最大值放到高下标区最终高下标区存放的是从大到小的序列整体就是升序。C 语言实现void heap_sort(int *a, int n) { // 1. 原地建大顶堆 // 这里不用调用 Heap 结构体直接对数组操作 // 建堆从最后一个非叶子节点 n/2 - 1 开始下标从 0 开始的版本 // 为了统一下面使用下标从 0 开始的版本演示 // 建堆 for (int i n / 2 - 1; i 0; i--) { // 下沉sift_down(a, i, n) int k i; while (2 * k 1 n) { int j 2 * k 1; if (j 1 n a[j 1] a[j]) { j j 1; } if (a[k] a[j]) break; int tmp a[k]; a[k] a[j]; a[j] tmp; k j; } } // 2. 不断把堆顶交换到末尾 for (int len n - 1; len 0; len--) { int tmp a[0]; a[0] a[len]; a[len] tmp; // 对 a[0] 做下沉堆的大小是 len int k 0; while (2 * k 1 len) { int j 2 * k 1; if (j 1 len a[j 1] a[j]) { j j 1; } if (a[k] a[j]) break; int tmp2 a[k]; a[k] a[j]; a[j] tmp2; k j; } } }这段代码没有复用之前的Heap结构体直接在数组上操作。这样做的理由是堆排序是原地排序不需要额外的动态内存用结构体反而多一层封装。实际工程里这两种写法都有我觉得初学最好把两种都写一遍——带结构体的版本练习堆的操作本身的正确性直接对数组操作的版本练习原位调整的细节。堆排序的时间复杂度是稳定的 O(n log n)建堆 O(n)n-1 次下沉每轮 O(log n)合计 O(n log n)。空间复杂度 O(1)。它和快速排序相比最显著的特征是时间复杂度与数据初始分布无关无论数据是有序的还是乱序的它都是那么稳定不会出现快排那种 O(n²) 的退化场景。代价是内部循环操作较多常数因子比快排大在大多数硬件实测中通常比快排慢一点。4.2 TopK 问题海量数据里找最大/最小的 K 个这里有个非常经典也极具迷惑性的问题找数组中最大的 K 个数用大顶堆还是小顶堆很多人第一反应是要最大的 K 个数当然用大顶堆每次把最大的顶上去。但这是错的。正确做法是维护一个大小为 K 的小顶堆遍历数组时如果当前元素比堆顶大就替换堆顶并下沉遍历结束后堆里的 K 个元素就是最大的 K 个数。为什么用小顶堆因为小顶堆的堆顶是堆里最小的元素也就是当前最大的 K 个数中最小的那个——也就是 K 个最大数的门槛。新元素只有比这个门槛大才有资格进入前 K。每次淘汰门槛堆中新加入的元素就是当前数组里更大的候选者。用小顶堆我们始终能知道当前最小的门槛是谁从而决定要不要把它换掉。如果用大顶堆堆顶是最大数新元素来了你没法判断它能不能进前 K——你必须要和 K 个最大的数中最小的那个比而大顶堆给不了你这个信息。复杂度方面遍历 n 个元素每个元素最坏情况触发一次 O(log K) 的下沉总复杂度 O(n log K)空间 O(K)。在 K 远小于 n 的场景比如从 10 亿数据里找前 100非常划算。这段代码可以直接用前文的Heap结构体按小顶堆初始化然后写一个循环替换void find_topk(int *a, int n, int k, int *result) { Heap *h heap_create(k, 0); // 小顶堆 for (int i 0; i n; i) { if (h-size k) { heap_push(h, a[i]); } else if (a[i] heap_top(h)) { heap_pop(h); heap_push(h, a[i]); } } // result 数组保存堆里的 k 个元素需要的话再排个序 for (int i 0; i k; i) { result[i] h-data[i 1]; } heap_free(h); }注意result里保存的元素顺序不是有序的就是堆的无序存储顺序。如果要按从大到小输出可以先 pop 全部元素构造一个有序序列或者额外做一个排序。别漏掉这个细节我见过不少人拿堆内部数组的顺序直接当作答案输出结果发现顺序不对。4.3 动态数据流的中位数两个堆配合的进阶玩法TopK 已经算是常见应用了但堆还有一个非常漂亮的技巧——用一个大顶堆和小顶堆配合在动态数据流中维护中位数。思路是维护两个堆大顶堆保存较小的一半数小顶堆保存较大的一半数并且保证大顶堆的大小要么等于小顶堆要么比小顶堆多一个。这样中位数就是大顶堆的堆顶奇数个数时或者大顶堆和小顶堆堆顶的平均值偶数个数时。插入新元素时先和大顶堆堆顶比较决定进哪个堆然后通过堆之间的元素移动来维持两个堆的大小平衡。整个过程每个元素进堆 O(log n)取中位数 O(1)。这里有个关键细节两个堆的大小差不能超过 1。如果大顶堆比小顶堆多 2 个以上就把大顶堆堆顶弹出压入小顶堆反过来也一样。移动后两个堆的内部结构都会被自动调整因为它们本身就是堆。这个场景在实时统计、在线排行榜等场景中很常见。我最早在做一个股票价格模拟系统时用过这个思路——数据以流的形式不断到达需要随时知道当前价格的中位数。如果用排序数组做每次插入都是 O(n)用两个堆做每个操作都是 O(log n)实测百万级数据量时差距接近几个数量级。5. 堆和栈、堆内存的辨析面试和实战中的高频误区这一节我专门写给即将面试或正在做期末复习的读者。作为一个经常当面试官的人我可以告诉你堆和栈有什么区别这个问题十个候选人里至少有三个会把数据结构的堆和内存的堆搅在一起。下面把这些概念一次性理清。5.1 数据结构角度堆 vs 栈数据结构层面栈是一种 LIFO后进先出的线性结构操作受限——只能在栈顶压入和弹出。堆是一种树形结构支持 O(log n) 插入和 O(log n) 删除极值。两者唯一的共同点是都叫堆/栈以及都是容器其余没有任何直接关系。面试时一旦被问到堆和栈的区别你应该先反问一句您问的是数据结构层面还是内存分布层面这样既展示了你概念的清晰度也把问题引向更明确的讨论方向。数据结构栈最常见的应用是函数调用栈、括号匹配、表达式求值堆最常见的应用是优先队列、调度算法、堆排序。5.2 内存角度堆区 vs 栈区内存分布层面程序运行时栈区和堆区是进程虚拟地址空间中两个不同的区域栈区由编译器自动分配和释放存放局部变量、函数参数、返回地址等。它的分配和释放效率极高只需要移动栈顶指针但空间有限递归过深或声明过大的局部数组就会栈溢出。堆区由程序员手动申请和释放存放动态分配的内存。空间更大、更灵活但需要手动管理生命周期否则就是内存泄漏。malloc/new分配的内存就在堆区。运行时报错 stack overflow 基本就是栈空间不够用heap 空间不足则是堆区内存耗尽。前者最常见的原因是递归无终止条件或局部数组太大后者最常见的原因是大量内存申请后没有释放累积导致堆空间枯竭。5.3 常见误区清单下面我把这些年见过的错误说法整理成一个清单每条后面给出正确解释误区正确理解堆就是malloc的那块内存malloc分配的内存确实来自堆区但堆首先是数据结构术语两者命名撞车栈比堆快从内存分配/释放机制看栈确实比堆快自动管理 vs 手动管理但这是内存层面的结论与数据结构无关大顶堆就是最大值堆对但堆里不是所有元素都有序堆顶才是极值堆排序一定比快排快错堆排序时间复杂度稳定但常数因子更大多数实测慢于快排TopK 最大 K 个用大顶堆错用小顶堆维护门槛才是正确选择这些误区之所以普遍本质上还是因为堆这个词被两个不同领域复用了。你只要记住讨论数据结构时堆完全二叉树堆序性质讨论内存时堆动态内存区域。分清这一点后面很多困惑都会消失。5.4 面试题里堆的难度梯度如果是校招/实习生级别最常见的是实现堆排序、用堆求 TopK、手写优先队列。社招的话更侧重场景设计比如如何在海量日志中找到出现频率最高的前一百个词——本质上还是 TopK但要先做词频统计再进堆。再高级一点会问求实时数据流的中位数就用到两个堆配合的技巧。我个人的建议是面试前除了把插入删除和堆排序写熟一定要能讲清楚为什么建堆是 O(n)以及为什么 TopK 要用小顶堆这两个推导过程。面试官问堆大概率就是看你能不能讲清楚这两个为什么。光会写代码而说不清原理的候选人在我这里最多拿一半分。6. 写堆代码的调试经验与性能优化细节最后这部分全是实操层面的经验。堆的实现代码不长但它有两个特点一是边界条件多二是状态隐含在数组里肉眼不容易发现问题。基于我实际调试的经历分享几个最有价值的判断方法和优化思路。6.1 堆代码最常见的三类 bug 及排查方法边界条件类 bug。最典型的是左孩子是否存在的判断写错。下标从 1 开始左孩子是2k但2k可能超过堆大小n此时当前节点是叶子下沉应该终止。我把这个条件写错过几次表现出来就是小数据测试正常数据量一大就出现堆顶不是极值的错误。排查方法是构造边界数据插入一个元素、插入两个、三个……手动走一遍代码比随机数据更容易暴露边界问题。下标混淆类 bug。前面提到过sink(h, 1, h-size)里的第三个参数到底是堆大小还是数组容量是重灾区。堆排序时尤其容易混——因为排序过程中堆的有效大小和数组长度是两个概念。我的习惯是函数签名里凡是用到长度的参数一律取名为n和count不用size因为在Heap结构体里size已经隐含了当前堆大小的意思函数参数再用它会增加迷惑性。结构体生命周期类 bug。realloc之后没有更新capacity、heap_free后没有置空指针、扩容时忘记多分配一个空间下标 0 不用。这类 bug 通常在压力测试下才暴露。我的建议是在heap_resize里加入容量检查如果size快接近capacity就提前扩容不要等到插入时才想起来检查。这类防御式编程能帮你减少大量无谓的排查时间。6.2 复杂度分析与优化方向堆的各项操作复杂度需要烂熟于心操作时间复杂度取堆顶O(1)插入O(log n)删除堆顶O(log n)建堆O(n)堆排序O(n log n)优化方向上有一个不太多人注意的点如果堆的底层数组频繁插入删除导致频繁realloc性能损耗很明显。我的做法是在初始化时根据数据量预估一个初始容量比如预计处理 10 万数据就heap_create(100000, 1)后面基本不需要扩容。如果实在无法预估扩容策略用翻倍而不是每次加固定大小这样摊还复杂度是 O(1)。还有一个优化叫做索引堆Index Heap适合处理需要更新堆中某个已有元素的优先级的场景。普通堆一旦元素入堆后你不知道它在数组的哪个位置无法直接修改它。索引堆额外维护一个位置数组记录每个元素的索引从而支持 O(log n) 的修改操作。这个在 Dijkstra 最短路径算法的堆优化版本里非常关键。如果你已经能熟练写出普通堆可以去研究一下索引堆的改进思路——它能帮你对堆的本质是下标映射有更深的理解。6.3 什么时候不该用堆这是一个容易被忽略但同样重要的问题。堆不是万能的以下场景你应该考虑其他数据结构需要按任意顺序遍历所有元素。堆只保证堆顶是极值遍历时如果你想输出有序序列需要不断 pop得到的是有序序列但内部数组本身并不是完全有序的。此时直接用排序数组更合适。需要快速查找某个具体值是否存在。堆的查找是 O(n) 的没有任何索引可以利用。这种场景应该用哈希表或平衡树。数据量极小几十个元素。线性扫描找出最大值的开销远小于建堆加维护堆序的开销。堆的 O(log n) 优势只在 n 足够大时才能抵消常数因子。判断该不该用堆本质上是一个操作频率问题你的场景是否高频执行插入取极值如果是堆是你的首选如果不是排序或线性扫描可能更简单也更划算。6.4 从手写堆到标准库的过渡一旦通过手写堆理解了底层原理日常开发中强烈推荐直接用语言的标准库——C 的std::priority_queue、Python 的heapq、Java 的PriorityQueue这些实现经过生产环境千万级验证边界条件处理得远比你自己写的健壮。但这里有个自我检验的建议你在标准库里要能看懂入参含义是什么、比较器怎么定义、默认是大顶堆还是小顶堆。以 C 为例std::priority_queueT默认是大顶堆靠的是lessT比较器如果你要小顶堆就要传入greaterT。很多人在这一步不知所措——因为他们只记得调库不知道堆的语义跟less/greater的关系。理解了本文中的higher函数之后再看标准库比较器就豁然开朗了底层逻辑完全一样标准库只是把这个函数抽象成了模板参数。我自己玩堆的最大收获其实是看任何数据结构先找它的不变量——堆的不变量就是堆序性质所有操作的维护都在保护这个不变量。一旦抓住这个核心后面学跳表、B 树、红黑树思路都会非常清晰。数据结构之间的差异说到底就是不变量不同、维护手段不同、操作代价不同而已。