“数据结构二叉树-堆”这个标题说实话有点误导性。很多人一看“堆”两个字条件反射想到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 - 10基。为什么是它因为从 n/2 到 n-1 这些节点全都是叶子节点叶子没有孩子下沉毫无意义。直接从倒数第二层开始从下往上处理保证每个节点处理时它的左右子树已经是合法的堆这是从底向上递推的关键。注意写循环方向时一定要搞清楚“从后往前”还是“从前往后”。Heapify 必须从后往前遍历非叶子节点如果从前往后会出现上面修好了、下面又坏了的问题因为你的子树还没变成合法的堆。2.4 操作复杂度与关键参数分析把堆的基本操作汇总成一张对照表方便复习和笔试参考操作时间复杂度空间复杂度说明取堆顶O(1)O(1)数组第0个或第1个元素插入O(log n)O(1)末尾追加 上浮删除堆顶O(log n)O(1)末元素补位 下沉建堆heapifyO(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、2i1、2i2核对公式随机崩溃 / 数据被篡改扩容时realloc失败、越界写破坏了相邻内存用valgrind或AddressSanitizer检测内存问题死循环下沉/上浮的循环终止条件写错在循环里打印i和child值观察是否反复横跳我个人排查二叉树问题时有一个很笨但很有效的办法在递归函数入口打印三个信息——“当前节点值、节点地址、来自父节点哪一侧”。递归树结构一旦有环路比如某个节点的child指向了自己的祖先打印出来的调用序列就会无限重复一眼就能看出来。提示写任何二叉树结构先写好“析构/清理函数”和“断言工具函数”。比如打印整棵树结构的函数、校验堆序性的函数调试时不丢人反而能帮你省一整晚的时间。我维护过一段堆代码里面就放了一个assert_heap_valid(h)每次push和pop之后都调用它出问题立刻定位不用满世界找bug。关于二叉树和堆我再多说一句心得体会。堆这个结构代码不多十几二十行就能写完但它特别考验你对“局部有序”和“全局有序”的理解。我见过不少同学背熟了堆排序代码一问到“为什么堆不能像搜索树那样查找某个值”就卡壳原因就是没真正想清楚“堆只约束父子、不约束兄弟”这件事。把这一点想透了优先队列、Top K、双堆中位数这些应用题你一眼就能看穿它的底牌。最后分享一个我自己的小技巧学堆的时候别只在脑子里模拟。拿一副扑克牌打乱顺序按层序遍历摆成一棵完全二叉树然后亲手模拟一次向上调整和向下调整。你只需要亲手走一遍那些下标公式、比较方向、边界条件就全都活了。以后不管是手写堆排序还是调PriorityQueue都会比别人稳得多。