数据结构‑二叉树（二）：二叉堆从零实现｜Heap结构设计 + 建堆优化 + 堆排序深度解析-北京尧图网络

写在前面上一篇数据结构-二叉树一树的基础概念与二叉树核心结构-CSDN博客我们学习了树、二叉树以及完全二叉树并得到数组存储下父子下标公式左孩子left parent * 2 1右孩子right parent * 2 2父节点parent (child - 1) / 2堆就是建立在完全二叉树之上的数据结构它把树形逻辑映射到连续数组高效维护集合的最大值/最小值。堆不只是课堂考点工程中大量使用堆排序、Top‑K问题、优先级队列、操作系统任务调度、Dijkstra最短路径算法都离不开它。本文基于C语言完整实现0下标二叉堆讲解Heap结构体设计为什么传结构体指针向上调整、向下调整核心逻辑与易错坑向上建堆 vs 向下建堆时间复杂度对比大小根堆切换方法堆排序原理搞懂「降序建小堆升序建大堆」排序算法横向对比多组测试用例解读与常见踩坑。代码仓库数据结构/Heap · Luminous/Code_2026 - 码云 - 开源中国一、什么是堆Heap堆是特殊的完全二叉树只约束父子节点的大小关系整棵树并不全局有序这点是绝大多数初学者的误区。小根堆任意父节点的值 ≤ 子节点的值堆顶根一定是整个集合最小值。7 / \ 12 45 / \ 89 23底层数组{7,12,45,89,23}大根堆任意父节点的值 ≥ 子节点的值堆顶根一定是整个集合最大值。89 / \ 45 56 / 23特别注意堆不是有序数组。示例1 / \ 5 3 / 8满足小根堆性质但数组{1,5,3,8}并不是升序。堆只保证父子关系不保证左右子树、兄弟节点之间有序。堆的优势(O(1))拿到极值想要整体有序需要堆排序。二、堆的存储与结构体设计逻辑上是完全二叉树但不使用链式TreeNode节点。完全二叉树几乎没有空间浪费直接用一段连续动态数组存储效率更高。typedef int HPDataType; typedef struct Heap { HPDataType* a; // 动态数组存放堆元素 int size; // 当前有效元素个数 int capacity; // 数组总容量 }Heap;a动态开辟的数组也可以直接挂载外部已有数组实现原地建堆size堆的有效元素[0,size‑1]为有效区间capacity数组总容量用于判断是否需要realloc扩容。内存示意capacity8size5[7][12][45][89][23][ ][ ][ ]三、接口为什么传Heap*指针不传Heap值拷贝函数原型对比// 传值操作副本外面堆不会变化 void HeapPush(Heap hp, int x); // 传指针操作原堆对象 void HeapPush(Heap* hp, int x);三点设计原因修改原堆对象插入、删除会修改size、a指针。传值会生成结构体副本函数内部修改全部作用在副本上外部堆完全不受影响逻辑失效。减少拷贝开销虽然结构体本身不大但传值会完整复制结构体传指针只传递地址开销恒定。核心支持外部数组复用原地建堆这是HeapCreate接口设计的关键。可以直接把外部普通数组挂载到hp-a不需要malloc新空间、不需要拷贝数据。int arr[] {12,45,7,89,23,56}; HeapCreate(hp, arr, 6); // hp-a直接指向arr原地建堆省去内存分配与拷贝也是堆排序可以做到(O(1))额外空间的底层思想。四、堆调整核心思想为什么需要向上和向下调整堆的本质要求任意节点都必须满足父节点和孩子节点之间的大小关系。以小根堆为例父节点 ↓ 父 ≤ 子 7 / \ 12 45但是在实际操作过程中插入元素只能破坏从新增节点到根节点这一条路径删除堆顶只能破坏从根节点到叶子节点这一条路径因此没有必要重新遍历整棵树只需要沿着一条路径调整即可。这就是堆高效的原因利用完全二叉树高度为 log N 的特点只需要调整一条路径。4.1 向上调整新元素插入后的维护使用场景HeapPush插入元素例如当前小根堆10 / \ 20 30 / 40数组[10,20,30,40]现在插入新元素5。按照完全二叉树规则新元素只能接在末尾10 / \ 20 30 / \ 40 5对应数组[10,20,30,40,5]此时发现5 20破坏小根堆性质10 / \ 20 30 / 40 / 5所以需要让新元素不断向上移动。向上调整过程第一次交换10 / \ 5 30 / 40 / 20继续比较5 10继续交换5 / \ 10 30 / 40 / 20最终恢复小根堆5 / \ 10 30 / 40 / 20向上调整代码对应逻辑while(child 0) { parent(child-1)/2; if(a[child] a[parent]) { Swap(a[child],a[parent]); childparent; } else { break; } }核心逻辑孩子违反规则 ↓ 和父节点交换 ↓ 继续向上检查插入只能影响新增节点到根节点路径因此使用向上调整。时间复杂度树高度 h log N最坏一路交换到根单次调整 O(log N)。4.2 向下调整删除堆顶后的维护使用场景HeapPop删除堆顶例如小根堆5 / \ 10 20 / \ 30 40数组[5,10,20,30,40]如果直接删除堆顶元素5树形结构直接残缺? / \ 10 20 / 30完全二叉树结构被破坏不能直接删除根。正确操作分为两步第一步交换堆顶和最后元素交换5 ↔ 4040 / \ 10 20 / 30数组变为[40,10,20,30]此时树形结构完整但堆性质被破坏。第二步让40向下移动左右孩子比较10 20选择更小的孩子10。交换父与子10 / \ 40 20 / 30继续比较40 30再次交换10 / \ 30 20 / 40堆性质恢复。向下调整代码思想child parent*21; while(childsize) { //找到更优孩子 //父子比较 //交换 parentchild; }核心逻辑父节点违反规则 ↓ 选择更小/更大的孩子 ↓ 交换 ↓ 继续向下删除堆顶只影响根节点到叶子的路径所以使用向下调整。时间复杂度O(log N)五、堆基础接口实现初始化、销毁void HeapInit(Heap* hp) { assert(hp); hp-a NULL; hp-size 0; hp-capacity 0; } void HeapDestory(Heap* hp) { assert(hp); free(hp-a); hp-a NULL; hp-capacity hp-size 0; }特别注意HeapCreate挂载栈数组时栈内存不能free销毁前务必手动置空hp-a NULL否则程序崩溃。堆插入 HeapPush尾插元素容量不足则二倍realloc扩容新元素做向上调整。单次插入(O(\log N))。void HeapPush(Heap* hp, HPDataType x) { if (hp-capacity hp-size) { int num hp-capacity 0 ? 4 : hp-capacity * 2; HPDataType* tmp (HPDataType*)realloc(hp-a, sizeof(HPDataType) * num); if (tmp NULL) { perror(realloc fail); exit(-1); } hp-a tmp; hp-capacity num; } hp-a[hp-size] x; hp-size; HeapAdjustUp(hp-a, hp-size-1); }删除堆顶 HeapPop不能直接删除数组下标0会破坏完全二叉树结构。正确流程堆顶与末尾元素交换 → size‑1逻辑删除末尾 → 对根做向下调整。单次删除(O(log N))。void HeapPop(Heap* hp) { assert(hp); assert(hp-size 0); Swap(hp-a[0], hp-a[hp-size-1]); hp-size--; HeapAdjustDown(hp-a, hp-size, 0); }取堆顶、判空HPDataType HeapTop(Heap* hp) { assert(hp); assert(hp-size 0); return hp-a[0]; } bool HeapEmpty(Heap* hp) { assert(hp); return hp-size 0; }六、两种建堆方式详细对比如果现在给你一个无序数组int a[]{12,45,7,89,23,56};如何把它构建成堆存在两种实现思路。6.1 方法一向上调整建堆思想假设前面的元素已经是堆不断插入新元素。推演过程初始12加入4512 \ 45满足堆性质。加入7数组[12,45,7]12 / \ 45 77 12违反小根堆进行交换7 / \ 45 12继续加入897 / \ 45 12 / 89继续加入237 / \ 23 12 / \ 89 45最终形成小根堆7 / \ 23 12 / \ 89 45对应代码for(int i1;in;i) { HeapAdjustUp(a,i); }每新增一个元素就做一次向上调整单次最多 log N。总时间复杂度O(N logN)。6.2 方法二向下调整建堆推荐思想叶子节点天然满足堆只需要调整非叶子节点。数组12 45 7 89 23 56对应完全二叉树12 / \ 45 7 / \ / 89 23 56叶子节点89、23、56叶子不需要调整。从最后一个非叶子节点向前处理。最后非叶子节点下标(n‑2)/2本例(6‑2)/2 2。1处理下标2节点7 / 56满足堆无需交换。2处理下标1节点45 / \ 89 23孩子23更小执行交换23 / \ 89 453处理下标0节点12 / \ 23 7 / \ / 89 45 56孩子7最小执行交换7 / \ 23 12 / \ / 89 45 56小根堆建立完成。为什么向下建堆是 (O(N))很多人直觉认为每个节点调整代价 log N总复杂度就是 O(N log N)这个理解是错误的。原因在于不同层节点数量、调整次数不一样底层节点数量最多但高度为0几乎不用向下调整越靠近上层节点数量越少但向下调整步数变多。求和拿到完整数组时优先选择向下调整建堆。建堆方式最终总结方式核心思想复杂度适用场景向上建堆模拟不断Push插入O(N log N)动态逐个插入元素向下建堆从最后非叶子节点向前调整(O(N))已有完整数组原地建堆七、堆排序深度解析重点区分建堆O(N)完整堆排序整体(O(N logN))。堆排序分为两步将无序数组建堆不断把堆顶极值交换到数组尾部尾部区间逐步有序前面区间继续向下调整维护堆。void HeapSort(int* a, int n) { // 降序建小堆 // 升序建大堆 //for (int i 1; i n; i)//向上调整 O(N*logN) //{ // HeapAdjustUp(a, i); //} //向下调整建堆 O(N) for (int i (n - 1 - 1) / 2; i 0; i--) { HeapAdjustDown(a, n, i); } int end n - 1; while (end 0) { Swap(a[0], a[end]); HeapAdjustDown(a, end, 0); --end; } }核心口诀降序建小堆升序建大堆很多同学在这里记反推导逻辑堆顶永远是当前区间的极值每次把堆顶交换到数组末尾末尾位置就排好序不再参与后续堆调整。建小根堆堆顶是最小值。最小值不断放到数组末尾尾部依次存放最小、次小……最终整体数组降序。建大根堆堆顶是最大值。最大值不断放到数组末尾尾部依次存放最大、次大……最终整体数组升序。复杂度拆解建堆阶段O(N)while循环执行n‑1次每次向下调整(O(log N))(O(N log N))总复杂度 TO(N)O(N log N)O(N log N)大O表示法保留高阶项。空间复杂度(O(1)) 原地排序稳定性不稳定排序。八、排序算法横向对比算法平均时间最坏时间额外空间稳定性评价冒泡排序O(N^2)O(N^2)(O(1))稳定仅教学大数据量性能极差堆排序O(N log N)O(N log N)(O(1))不稳定最坏情况性能稳定内存友好缓存局部性较差快速排序O(N log N)O(N^2)O(log N)递归栈不稳定实际运行最快语言内置排序核心常数因子小堆排序最坏时间不会退化但实际跑的速度一般弱于快排。堆真正强项不是完整排序而是Top‑K、优先级队列场景。Top‑K简单理解海量数据求前K大元素不需要全部排序。维护大小为K的堆复杂度O(N log K)K远小于N的时候比全局排序O(N log N)效率高很多。九、项目代码结构与test.c测试解读项目三层文件拆分Heap.h结构体、函数声明Swap为内部辅助函数不对外暴露Heap.c全部接口实现默认小根堆test.c三组测试同一时间只启用一组main其余注释。测试1裸数组原地堆排序求前K大元素当前启用直接操作普通数组不使用Heap结构体原地完成堆排序排序完成数组降序数组前k个即为前k大元素。注释保留向上调整建堆代码用于对比学习。测试2堆接口Push/Pop整套功能测试完整验证初始化、插入、弹出、堆顶、判空、销毁。当前是小根堆弹出顺序从小到大切换大根堆后输出会改变。测试3拷贝堆数组不破坏原堆求前k大malloc复制一份堆内存在副本上执行Pop取TopK原始堆数据不受影响。注意tmpHp只是借用malloc出来的内存不要调用HeapDestory(tmpHp)手动free拷贝内存即可避免二次释放。代码仓库已经上传本篇及以往博客代码可以拉取代码学习使用。数据结构/Heap · Luminous/Code_2026 - 码云 - 开源中国十、常见坑点汇总0下标堆父子公式不要和1下标混用混用直接逻辑错乱大小根堆三处比较符号必须同步修改否则堆性质失效HeapCreate挂载栈数组销毁前hp-a NULL禁止free栈内存Pop不能直接删除下标0必须交换堆顶与末尾元素再向下调整已有完整数组建堆优先向下调整建堆O(N)不要向上调整区分概念建堆O(N)堆排序整体(O(N logN))不要混淆两个复杂度。写在最后从树形结构到数组存储从堆调整到堆排序二叉堆看似只是完全二叉树的一种特殊形式但背后体现的是数据结构中非常重要的思想利用结构特点降低操作成本。本篇重点掌握了几个核心堆本质是完全二叉树通过数组实现避免了链式结构的额外空间开销向上调整解决「插入后维护堆性质」的问题向下调整解决「删除堆顶以及建堆」的问题已有完整数组时优先使用向下调整建堆时间复杂度从 (O(N logN)) 优化到 (O(N))堆排序虽然实际效率通常不如快速排序但它拥有稳定的最坏情况复杂度和 (O(1)) 空间优势堆真正强大的地方并不是排序而是在动态维护极值例如 Top-K、优先级队列、任务调度等场景。学习数据结构时不应该只停留在记忆代码和复杂度更重要的是理解每个设计背后的原因为什么完全二叉树适合数组存储为什么插入使用向上调整删除使用向下调整为什么建堆推荐从最后一个非叶子节点开始为什么堆排序选择大根堆或小根堆会影响最终排序方向当这些问题真正理解后堆就不再是一段需要背诵的代码而会成为解决实际问题的一种工具。下一篇将继续深入二叉树专题学习二叉树的遍历、递归思想以及更多经典应用。从基础结构出发逐步构建数据结构与算法能力体系。

数据结构‑二叉树（二）：二叉堆从零实现｜Heap结构设计 + 建堆优化 + 堆排序深度解析

相关推荐

Agent系列

从“语义翻译官”到“全模态记忆中枢”：嵌入模型的技术原理、演进脉络与2026年全景剖析

还拿Linux那套来玩银河麒麟？防火墙根本不是同一个东西！

更多资讯

[deprecated]第六章：异步访问的同步：6.4.3 libdrm 中 drm_syncobj 的实现分析

[deprecated]第六章：异步访问的同步：6.4.2 drm_syncobj 机制原理与内核实现

TDD测试驱动开发：自学是门手艺写给初学者的完整入门指南

Chisle规则集注入机制揭秘：SessionStart钩子、900 Token瘦身与自动降级策略

罗技G HUB（Logitech G HUB）旧版本驱动下载地址大集合

SleekXMPP: Python库，用于处理XMPP协议的多功能工具

今日更新

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？