“数据结构：二叉树-堆”这个标题，说实话有点误导性。很多人一看“堆”两个字，条件反射想到JVM内存溢出、进程堆大小调整、OutOfMemoryError——这些热词在搜索引擎里跟“堆”纠缠得特别厉害。但把“堆”放在“数据结构”和“二叉树”后面，它指的完全是另一回事：一种形态特殊的二叉树，通常用数组实现，是优先队列、堆排序、Top K问题、中位数查找这些经典场景的底层核心。这篇文章我就把这棵树彻底拆开，讲清楚它为什么用数组存、上浮下沉是怎么回事、手写堆有哪些坑、以及它跟“内存堆”“堆栈”这些同名概念到底差在哪里。适合正在学《数据结构》做期末复习的同学、准备考研408的选手，以及工作中偶尔要手搓优先队列的工程师。
1. 堆到底是什么：从“二叉树”到“二叉堆”的距离
1.1 一棵“形态固定”的二叉树
堆首先是一棵二叉树，但不是随便什么形态的二叉树。它必须是一棵完全二叉树（Complete Binary Tree），这是第一个硬性约束。什么叫完全二叉树？简单说：除了最底层，上面每一层都是满的，最底层的节点全部向左靠拢、连续排列，中间不能有空缺。
为什么要卡这个形态？因为完全二叉树有一个极其优雅的性质：它的节点可以按层序遍历的顺序，一一映射到连续数组的下标上。你不需要像普通二叉树那样用left、right指针去串节点，直接用一个一维数组，就能完整表达整棵树的父子关系。这个性质是所有堆操作高效的前提。
普通二叉树则完全没有这个保证。你随便挂几个节点，形态千奇百怪，层序编号之后中间会出现空洞，数组存储就会浪费空间、下标关系也会失效。所以堆选完全二叉树，不是审美偏好，是数学结构决定的。
1.2 数组存堆：下标里的父子关系
既然堆是“完全二叉树 + 数组”，那么父子节点之间的定位就全看下标了。这里有两个习惯，工程实现里两种都有人用，务必分清楚：
如果数组下标从0开始：
- 第 i 个节点的左孩子：2 * i + 1
- 右孩子：2 * i + 2
- 父节点：(i - 1) / 2
如果数组下标从1开始（第0个位置留空不用）：
- 第 i 个节点的左孩子：2 * i
- 右孩子：2 * i + 1
- 父节点：i / 2
第二种在数学上更干净，很多教材和经典实现（比如《算法导论》《数据结构（C语言版）》）都用1基索引，因为 i/2 直接整除就能拿到父节点，不用处理边界。但现实里0基索引更符合C语言的数组习惯，所以我平时写代码倾向用1基，写排序算法做原地堆化时用0基。你在网上看到的代码这两种都有，看懂公式差别，才能不被下标搞晕。
注意：不管用哪种下标习惯，关键在于“完全二叉树层序连续”这个前提。一旦堆的形态被破坏，下标公式就全部失效，所有操作都会越界或错位。这是手写堆时最容易埋雷的地方。
1.3 大根堆与小根堆：堆序性的两种取向
形态是“完全二叉树”，只是堆的骨架。堆还差一层约束，叫堆序性（Heap Property）：
- 大根堆（最大堆）：每个节点的值都大于等于它的左右孩子。堆顶是整个堆的最大值。
- 小根堆（最小堆）：每个节点的值都小于等于它的左右孩子。堆顶是整个堆的最小值。
请你注意，堆序性只约束了“父子之间”的大小关系，完全没有约束“兄弟之间”的大小关系。左边孩子和右边孩子谁大谁小，堆不管。这也意味着堆不是一个“有序”的结构，它只保证“堆顶是最值”，并且沿着从根到叶子的任意一条路径，值是有序递减（或递增）的，但整棵树并不是全局有序的。
这一点跟二叉搜索树有本质区别。二叉搜索树要求左子树所有节点 < 根 < 右子树所有节点，这是全局有序性；堆只要求父 > 子，这是局部序。所以你在堆里没法像搜索树那样直接“查找某个值”，它的强项是快速取最值，而不是快速查任意值。
1.4 堆与普通二叉树、二叉搜索树的本质区别
我经常用一句话总结三者的关系：普通二叉树管“形态自由”，二叉搜索树管“全局有序”，堆管“最值快速可及”。
- 普通二叉树：形态不限，如果不加约束，最坏情况退化成单链表，查找变 O(n)。
- 二叉搜索树：通过中序遍历能得到有序序列，但需要额外维护平衡因子（如AVL、红黑树）来保证高度是 O(log n)。
- 堆：靠完全二叉树天然保证高度为 O(log n)，不需要旋转、变色之类的复杂平衡操作。但代价是它只能高效地获取最值，无法高效地查中间值、无法高效地遍历有序输出（除非不断删除堆顶）。
换句话说，堆牺牲了“全局有序”和“灵活查找”，换来了“极简维护 + 极速取最值”。这种取舍让它成为优先队列、调度器、Top K 问题的首选。
2. 堆的核心操作：上浮、下沉与建堆
堆的所有操作，归根结底都建立在两个基础动作上：上浮（Shift Up / Sift Up）和下沉（Shift Down / Sift Down）。这两个动作都是为了维护堆序性，理解了它们，堆就理解了80%。
2.1 上浮：插入操作的关键路径
插入一个元素时，堆的常规做法是：先把新元素放到数组末尾，也就是完全二叉树的最后一个位置。这一步能保证完全二叉树形态不被破坏。但新元素可能会违反堆序性——比如大根堆里，新元素比它的父节点还大，那它就得往上走。
上浮的过程就是：从当前位置出发，不断跟父节点比较，如果违反了堆序性（大根堆里子 > 父），就交换位置，继续向上，直到满足堆序性或到达根节点。
这里有个效率细节值得单独说：你不要真的用swap函数每轮交换一次。大部分教材用交换来讲解，逻辑清晰，但实际写代码时更高效的做法是“暂存待插入元素，把父节点逐步下移，最后把待插元素放到空位”。这样可以省掉一半的赋值操作，尤其是在节点数据很大（比如是结构体、字符串）时，性能差距会非常明显。这个技巧叫“移动空洞法”，写堆的人基本都这么干。
2.2 下沉：删除堆顶后的结构调整
删除堆顶（也就是取出最大值或最小值）是堆最核心的操作。你会想，直接把根节点删掉，然后把左孩子提上来？不行，这种野蛮做法会撕裂完全二叉树的结构，留下一堆空洞。正宗做法是：把数组最后一个元素移到堆顶，size减一。这样做的好处是，完全二叉树的形态再次被保全，只是堆顶这个“临时工”大概率不满足堆序性，需要往下调整。
下沉的逻辑是：从堆顶开始，找到左右孩子中更符合“上位条件”的那个（大根堆里找更大孩子，小根堆里找更小孩子），跟当前节点比较，如果违反堆序性，就交换，然后继续下沉到合适位置。
可以对比一下两个操作的差别：上浮只需要跟一个父节点比较，因为父节点只有一个；下沉则要先在两个兄弟里挑一个再比较，因为两个孩子谁更大/更小，决定了谁该上位。大根堆里如果左孩子大于右孩子，那左孩子上去；反之右孩子上去。如果两个都小于等于当前节点，说明当前位置合适，停止。
有一个常见错误是只跟左孩子比较，忘了右孩子也可能更大。尤其是当最后一个节点的索引恰好停在某个非叶子位置，右孩子为空时要小心边界。每轮选择孩子节点前都要判断右孩子下标是否越界。
2.3 建堆：逐个插入还是向下调整
假设你手上有一个无序数组，想把它变成堆，有两条路：
- 逐个插入：从空堆开始，依次对每个元素执行push操作。每个元素上浮 O(log n)，n 个元素总代价 O(n log n)。
- 向下调整建堆（Heapify）：从最后一个非叶子节点开始，从下往上依次对每个节点做下沉操作。
第二种方案你一定听说过，总体复杂度是 O(n)，不是 O(n log n)。为什么？直觉是这样的：堆的节点数量是“越靠近底层越多”，而每个节点下沉的代价是“越靠近底层越小”。底层大量节点只需要下沉0次或1次，只有接近根部的少量节点才需要下沉很多次。把每层节点的数量和下沉代价相乘再求和，是一个收敛的级数，结果趋近于 O(n)。这就是“多数节点干活少”带来的红利。
那么从哪里开始调整？最后一个非叶子节点，下标是 n/2 - 1（0基）。为什么是它？因为从 n/2 到 n-1 这些节点全都是叶子节点，叶子没有孩子，下沉毫无意义。直接从倒数第二层开始，从下往上处理，保证每个节点处理时它的左右子树已经是合法的堆，这是从底向上递推的关键。
注意：写循环方向时一定要搞清楚“从后往前”还是“从前往后”。Heapify 必须从后往前遍历非叶子节点，如果从前往后，会出现上面修好了、下面又坏了的问题，因为你的子树还没变成合法的堆。
2.4 操作复杂度与关键参数分析
把堆的基本操作汇总成一张对照表，方便复习和笔试参考：
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 取堆顶 | O(1) | O(1) | 数组第0个或第1个元素 |
| 插入 | O(log n) | O(1) | 末尾追加 + 上浮 |
| 删除堆顶 | O(log n) | O(1) | 末元素补位 + 下沉 |
| 建堆（heapify） | O(n) | O(1) | 从底向上逐节点下沉 |
| 堆排序 | O(n log n) | O(1) | 建堆 + 反复取堆顶 |
堆的“log n”高度完全由完全二叉树保证。n 个节点的完全二叉树高度严格等于 floor(log2 n) + 1，每层都是满的，所以不会出现二叉搜索树那种退化成链的极端情况。这也是堆不需要像AVL树那样额外做平衡维护的根本原因。
还有两个容易忽视的参数：一个是容量（capacity）和大小（size）要分开管理。C语言里实现动态数组时，size表示当前有效元素数，capacity表示分配的内存上限，元素个数到达capacity时需要扩容，扩容策略一般是翻倍，避免频繁realloc。另一个是“是否支持重复元素”，堆天然允许相等元素，但相等的元素在处理时是继续上浮还是停止，需要约定好，不然堆序性在某些边界条件下会抖动。
3. 手写一个二叉堆：完整C语言实现
光讲原理不过瘾，我直接给一份可以跑起来的C语言实现。整体用1基索引（data[0]闲置），小根堆为例，因为小根堆跟优先队列的默认行为一致。你要大根堆的话，把所有比较的符号反过来即可。
3.1 结构定义、初始化与扩容
#include <stdio.h> #include <stdlib.h> typedef struct { int *data; int size; int capacity; } Heap; void heap_init(Heap *h, int cap) { // 1基索引，下标0不用，所以实际分配 cap + 1 h->data = (int *)malloc(sizeof(int) * (cap + 1)); if (h->data == NULL) { fprintf(stderr, "malloc failed\n"); exit(1); } h->size = 0; h->capacity = cap; } void heap_destroy(Heap *h) { free(h->data); h->data = NULL; h->size = h->capacity = 0; } void heap_resize(Heap *h) { int new_cap = h->capacity * 2; int *new_data = (int *)realloc(h->data, sizeof(int) * (new_cap + 1)); if (new_data == NULL) { fprintf(stderr, "realloc failed\n"); exit(1); } h->data = new_data; h->capacity = new_cap; }扩容这里有个工程经验：realloc有可能返回的指针跟原来不一样，很多新手写成了h->data = realloc(h->data, ...)，万一realloc失败，原来的指针也丢了，造成内存泄漏。稳妥做法是先用临时指针接住返回值，判空后再赋给原指针，上面这段代码就是标准范式。
3.2 插入与删除堆顶的实现细节
void heap_push(Heap *h, int val) { if (h->size == h->capacity) { heap_resize(h); } int i = ++h->size; // 上浮：暂存val，父节点下移 while (i > 1 && h->data[i / 2] > val) { h->data[i] = h->data[i / 2]; i /= 2; } h->data[i] = val; }注意这个写法：不是每轮交换两个元素，而是先把父节点往下挪，最后才把val写进空位。这就是我前面说的“移动空洞法”。小根堆里，父节点大于新元素时，说明父节点该下去，就把父节点往下挪。循环结束后，i的位置就是val该待的位置。
int heap_pop(Heap *h) { if (h->size == 0) { fprintf(stderr, "heap underflow\n"); exit(1); } int top = h->data[1]; int last = h->data[h->size--]; int i = 1; int child; // 下沉：让last从堆顶开始往下找位置 while (i * 2 <= h->size) { child = i * 2; // 选更小的孩子（小根堆） if (child + 1 <= h->size && h->data[child + 1] < h->data[child]) { child++; } if (h->data[child] < last) { h->data[i] = h->data[child]; i = child; } else { break; } } h->data[i] = last; return top; }这里的选择逻辑要仔细看：child先指向左孩子，然后判断右孩子是否存在且更小，如果是就把child加1指向右孩子。先判断右孩子下标是否越界（child + 1 <= size），再比较值。顺序反了就会读到不存在的元素。
3.3 用堆排序跑通全流程
用这个堆结构做排序很简单：把所有元素push进去，再不断pop，因为是小根堆，pop出来的顺序就是升序。
void heap_sort_with_heap(int arr[], int n) { Heap h; heap_init(&h, n); for (int i = 0; i < n; i++) { heap_push(&h, arr[i]); } for (int i = 0; i < n; i++) { arr[i] = heap_pop(&h); } heap_destroy(&h); }这种写法空间复杂度是 O(n)，因为额外建了一个堆。如果你追求 O(1) 额外空间的原地堆排序，那就得换个思路：用0基索引，先原地建大根堆，然后每次把堆顶（最大值）与当前末尾交换，再把堆大小减一，对新的堆顶做下沉。反复执行到最后，数组就是升序的。
void sift_down_0(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp; sift_down_0(arr, n, largest); } } void heap_sort_inplace(int arr[], int n) { // 建大根堆 for (int i = n / 2 - 1; i >= 0; i--) { sift_down_0(arr, n, i); } // 反复交换堆顶和末尾 for (int i = n - 1; i > 0; i--) { int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; sift_down_0(arr, i, 0); } }原地版的关键是：每轮交换完成之后，末尾的最大值已经“出堆”，堆的有效范围减一。下沉时传入的n是当前堆的大小，不是整个数组长度。写错这个参数，排序结果会非常诡异。
3.4 这段代码的常见踩坑点
手写堆最容易翻车的地方我逐个点名：
- 容量满了忘扩容。如果push时的size等于capacity，直接往data[size]写，会越界写，内存被破坏。这个问题极其隐蔽，因为小数据量下可能碰巧没爆，一旦数据量上来就随机崩溃。
- 1基索引却把size初始化为0，但下标从1开始，写push时如果
h->data[++h->size]没有跟后续的i统一，会造成下标错位。建议心里默念三遍：1基索引，下标0闲置。 - 下沉循环的终止条件写错。
while (i * 2 <= h->size)表示还存在左孩子，如果写成while (i <= h->size / 2)要注意整数除法边界，容易漏判。 - 比较符号写反。小根堆上浮用父 > 子，下沉用子 < 父，符号全反就变成大根堆。排序方向不对，先检查比较符号，别急着怀疑算法。
- 弹出时size减到0之后再次pop。这是下溢，需要防御性判断，否则会读到data[1]这个悬空值。
4. 堆的核心应用：优先队列、Top K与中位数
4.1 优先队列：系统库的底层都是堆
优先队列是堆最经典的外衣。Java的PriorityQueue底层就是一个最小堆（默认自然序），C++的priority_queue默认是大根堆，Python的heapq模块直接暴露了堆操作接口。你可能每天都在用这些库，但库底层就是一个数组加一堆sift up / sift down。
优先队列解决的典型问题是“动态插入 + 每次取最值”。比如操作系统进程调度里的优先级队列、任务队列里的紧急任务优先，这些都是堆的用武之地。如果不用堆而用普通有序数组，插入一个元素要移动平均 n/2 个元素；用链表的话，取最值可能要扫全链表。堆在插入和取最值之间取得了完美平衡，都是 O(log n)。
4.2 Top K：海量数据里挑前K个
面试高频题“从海量数据中找出最大的K个数”。最简单粗暴的想法是全部排序取前K个，时间复杂度 O(n log n)，如果n是10亿，这基本不可接受。用堆的思路是：维护一个大小为K的小根堆，遍历数据时，如果当前元素比堆顶（当前K个里面最小的那个）大，就把堆顶替换掉，然后下沉。这样堆里始终保存着“已经见过的数据里最大的K个”，遍历完整个数据，堆就是答案。
这个方案的时间复杂度是 O(n log K)，当 K 远小于 n 时非常划算。更妙的是，它天然适合流式数据：数据不是一个数组整体给你，而是源源不断进来，你依然可以实时维护“当前最大的K个”。这个场景里，堆几乎是唯一解。
4.3 双堆求中位数：两个堆如何配合
另一个经典玩法：用一个大根堆存较小的一半数据，再用一个小根堆存较大的一半数据，保持两个堆的大小差不超过1。中位数就是两个堆顶之一或者两个堆顶的平均值。这就叫“双堆问题”（Two Heaps）。
具体流程：
- 新元素进来时，如果小于大根堆堆顶，说明它属于较小一半，进大根堆；否则进小根堆。
- 插入后检查两个堆大小，如果差大于1，把较大的堆顶移到另一个堆里。
- 取中位数时，如果两个堆大小相等，取两个堆顶的平均值；如果不等，取较大的堆的堆顶。
这套做法在动态数据流里特别优雅。你可以一边收数据，一边随时回答“当前中位数是多少”，每次操作 O(log n)，比每次重新排序快几个数量级。
4.4 定时器调度与更多场景
在写网络服务器、游戏服务器、延迟消息队列时，定时器是个绕不开的组件。最简单的实现是把所有定时任务放进一个小根堆，键是“触发时间戳”，堆顶永远是最早要触发的那个任务。每次循环取堆顶，判断当前时间是否到了触发时间，到了就执行并弹出，没到就继续等。比遍历所有任务判断时间要高效得多，也避免了每次都全量扫描。
除此之外，Dijkstra算法用优先队列实现时，每次从堆里取出“当前距离最短的未访问节点”，这就是著名的 Dijkstra with Heap 优化。Huffman编码建树时也要用小根堆来反复取两个最小值。你去看，凡是“频繁取最值 + 频繁插入”的地方，背后大概率站着一个堆。
5. 那些叫“堆”但不是堆的概念辨析
5.1 内存堆、堆栈、数据结构堆
这是初学阶段最混乱的一组概念。热搜词里的“堆外内存”“进程堆大小调整为8000”“java.lang.OutOfMemoryError”全都在说内存管理，跟数据结构里的堆没有一毛钱关系。
- 数据结构堆：一种树状逻辑结构，用数组实现，用来快速取最值。
- 内存堆（Heap，有的也叫堆区）：操作系统/语言运行时里动态分配内存的区域。C语言的malloc从堆区要内存，Java的new对象也分配在堆上。
- 调用栈（Stack）：函数调用时保存局部变量、返回地址的区域，后进先出。
为什么两边都叫“heap”？历史原因在于早期内存分配器用类似堆的数据结构来管理空闲内存块，叫“堆式分配”，后来“heap”这个名字就粘在了内存分配区上。但现代内存分配器早就不用二叉堆管理空闲块了，名字却保留了下来。你遇到heap size、OutOfMemoryError，调的是JVM参数或系统内存，跟二叉树堆算法没有半点关系。
5.2 二叉搜索树、线索二叉树和堆的关系与区别
复习《数据结构》的时候，二叉树这一章会同时出现二叉搜索树、线索二叉树、堆这几个概念，特别容易互相混淆，我做个对比：
| 结构 | 存储方式 | 有序性 | 核心操作 | 典型用途 |
|---|---|---|---|---|
| 二叉搜索树 | 链表式节点 | 全局有序：左 < 根 < 右 | 查找、插入、删除 O(log n) | 动态有序表、字典实现 |
| 线索二叉树 | 链表 + 前驱后继指针 | 中序有序（依赖线索） | 遍历 O(1) 找前驱后继 | 快速中序遍历 |
| 堆 | 连续数组 | 局部有序：父 > 子 | 取最值、插入、删除最值 O(log n) | 优先队列、Top K |
搜索树和堆都要求 O(log n) 高度，但搜索树靠“左右子树递归约束”维持全局有序，所以中序遍历能输出有序序列；堆靠“完全二叉树形态”保证高度，所以它只能保证堆顶是最值。如果你想从堆里中序遍历输出有序序列，对不起，做不到，只能不断弹出堆顶。
线索二叉树则是在普通二叉树节点里额外增加了线索指针（指向前驱和后继），目的是让中序遍历不用递归栈或栈结构就能线性完成。它跟堆的“数组连续存储 + 下标计算”是完全不同的两条设计路线。
5.3 写二叉树程序总是报运行时错误？排查思路实录
热词里有一条“写二叉树程序时为什么总是报运行时错误”，这几乎是所有初学者的噩梦。结合堆的实现，我把常见的运行时错误和排查方法整理成表：
| 报错现象 | 可能原因 | 排查思路 |
|---|---|---|
| 段错误 / Segmentation Fault | 空指针访问、野指针、malloc失败未处理 | 加断言：断言node不为NULL；打印指针值检查是否未初始化 |
| 栈溢出 / Stack Overflow | 递归深度过大（树高过大或递归终止条件缺失） | 检查递归基线条件；树是否退化成链表；印刷探针定位无限递归 |
| 数组越界 / 下标异常 | 堆下标公式用错、0基和1基混用 | 打印每次访问的i、2i+1、2i+2，核对公式 |
| 随机崩溃 / 数据被篡改 | 扩容时realloc失败、越界写破坏了相邻内存 | 用valgrind或AddressSanitizer检测内存问题 |
| 死循环 | 下沉/上浮的循环终止条件写错 | 在循环里打印i和child值，观察是否反复横跳 |
我个人排查二叉树问题时，有一个很笨但很有效的办法：在递归函数入口打印三个信息——“当前节点值、节点地址、来自父节点哪一侧”。递归树结构一旦有环路（比如某个节点的child指向了自己的祖先），打印出来的调用序列就会无限重复，一眼就能看出来。
提示：写任何二叉树结构，先写好“析构/清理函数”和“断言工具函数”。比如打印整棵树结构的函数、校验堆序性的函数，调试时不丢人，反而能帮你省一整晚的时间。我维护过一段堆代码，里面就放了一个
assert_heap_valid(h)，每次push和pop之后都调用它，出问题立刻定位，不用满世界找bug。
关于二叉树和堆，我再多说一句心得体会。堆这个结构代码不多，十几二十行就能写完，但它特别考验你对“局部有序”和“全局有序”的理解。我见过不少同学背熟了堆排序代码，一问到“为什么堆不能像搜索树那样查找某个值”就卡壳，原因就是没真正想清楚“堆只约束父子、不约束兄弟”这件事。把这一点想透了，优先队列、Top K、双堆中位数这些应用题，你一眼就能看穿它的底牌。
最后分享一个我自己的小技巧：学堆的时候，别只在脑子里模拟。拿一副扑克牌，打乱顺序，按层序遍历摆成一棵完全二叉树，然后亲手模拟一次向上调整和向下调整。你只需要亲手走一遍，那些下标公式、比较方向、边界条件就全都活了。以后不管是手写堆排序还是调PriorityQueue，都会比别人稳得多。
