一、什么是堆1.1基本概念堆本质是一棵完全二叉树但它的所有元素都存储在一维数组中物理结构上是顺序结构逻辑上是二叉树结构。注这里的“堆”是数据结构概念和操作系统内存管理的“堆区”是完全不同的两个概念堆满足两个核心性质1.是完全二叉树除最后一层外其余层节点数全满最后一层节点从左到右连续排列2.任意节点的值总是不大于或不小于其父节点的值。1.2大根堆vs小根堆1大根堆大堆任意父节点的值 ≥ 左右孩子节点的值堆顶根节点是整个集合的最大值2小根堆小堆任意父节点的值 ≤ 左右孩子节点的值堆顶根节点是整个集合的最小值本文代码默认以大根堆为例讲解小根堆仅需修改比较符号即可。1.3 顺序存储的父子下标公式堆用数组存储下标从 0 开始通过数学公式就能直接找到任意节点的父节点和孩子节点这是堆能高效操作的核心基础1已知子节点下标 child 父节点下标 parent (child - 1) / 22已知父节点下标 parent 左孩子下标 leftChild parent * 2 13已知父节点下标 parent 右孩子下标 rightChild parent * 2 2二、堆的接口功能声明(在Heap.h头文件中实现三、堆的结构体与基础接口除结构体定义外其余代码在Heap.c中实现3.1堆的结构体定义我们用动态数组来实现堆支持自动扩容。1. 用动态数组而非固定数组避免空间浪费和溢出问题支持任意规模的数据2. size 标记有效数据边界堆的所有操作都只在 [0, size-1] 范围内进行3. capacity 记录当前数组最大容量插入数据时判断是否需要扩容3.2堆的初始化与销毁1. 初始化时将指针置空、计数置0避免野指针2. 销毁时必须释放动态开辟的数组再将指针置空、计数清零防止内存泄漏3.3交换工具函数堆的调整操作中会频繁交换两个元素封装工具函数复用C语言的传值调用函数内修改形参不会影响外部变量因此必须传元素地址通过解引用直接修改原数组中的值。四、堆的核心两个调整算法堆的所有操作都依赖两个调整算法这是堆的灵魂。4.1向上调整算法AdjustUP适用场景入堆时新元素插在数组末尾二叉树最后一层叶子可能破坏堆性质需要让新节点向上浮到正确位置。核心思路从新插入的子节点出发不断和它的父节点比较如果不满足大堆规则子节点 父节点就交换二者然后继续向上层比对直到根节点或满足堆规则为止。1. 循环条件 child 0 根节点没有父节点走到根就停止2. 每次交换后要更新 child 和 parent 的下标继续向上比对3. 如果改成小堆只需把 改成 即可4.2向下调整算法AdjustDown适用场景出堆时堆顶元素被替换堆性质被破坏需要让新的堆顶节点向下沉到正确位置。核心思路从待调整的父节点出发先找到左右孩子中值更大的那个大堆再和父节点比较如果不满足大堆规则孩子 父节点就交换二者然后继续向下层比对直到叶子节点或满足堆规则为止。1. 先判断 child 1 n 防止右孩子不存在数组越界访问2. 循环条件 child n 走到叶子节点没有孩子就停止3. 这是堆操作中最高频的算法建堆、出堆、堆排序都依赖它五、堆的增删接口实现5.1入堆HeapPush步骤1. 先检查容量不够就扩容2. 把新元素放到数组末尾3. 对末尾新元素执行向上调整恢复堆性质5.2出堆HeapPop堆只能删除堆顶元素不能随便删除中间节点。标准步骤1. 把堆顶元素和数组最后一个元素交换2. 有效元素个数 size-- 相当于删掉了原堆顶3. 对新的堆顶执行向下调整恢复堆性质为什么不能直接删掉堆顶如果直接删除数组首元素后面所有元素都要前移时间复杂度 O(n)而且父子下标公式全部错乱堆结构直接崩溃。首尾交换向下调整的方式时间复杂度只有 O(logn)效率极高。5.3辅助接口取堆顶、判空、获取大小、打印堆六、接口功能测试在test.c中实现七、从测试用例引申堆排序的本质7.1先看测试用例test02堆的有序性雏形我们先写一段测试代码循环取出堆顶打印再弹出堆顶直到堆为空。运行后会输出 56 30 15 10 是一个降序的有序序列。这段代码其实就是堆排序的雏形——利用堆顶永远是最值的特性逐个取出最值就能得到有序序列。但它有个明显缺点需要额外构建一个堆结构占用 O(n) 的额外空间。那么能不能直接在原数组上完成排序不额外开空间这就是原地堆排序的核心思想。7.2堆排序的核心思想堆排序分为两大步1. 建堆把普通数组直接调整成合法堆1升序排序 → 建大根堆2降序排序 → 建小根堆2. 排序利用堆删除的思想把堆顶最值交换到数组末尾再对前面的区间向下调整重复操作直到整个数组有序第一步建堆的两种方式建堆有两种写法效率天差地别方式1逐个尾插 向上调整模拟入堆过程从第一个元素开始逐个向上调整时间复杂度 O(nlogn)方式2从最后一个非叶子节点倒序 向下调整叶子节点没有孩子天然满足堆规则不需要调整只需从倒数第二层最后一个节点开始从后往前逐个向下调整时间复杂度 O(n)效率更高是标准建堆方式。最后一个非叶子节点下标公式 (n-1-1)/2 也就是最后一个叶子节点的父节点。第二步排序过程以升序排序、建大堆为例1初始整个数组 [0, n-1] 是堆区间2把堆顶最大值和堆区间最后一个元素交换最大值就放到了数组末尾已排序区间3堆区间缩小为 [0, end-1] 对新堆顶向下调整4重复上述操作直到堆区间只剩一个元素数组整体有序7.3堆排序代码实现一句话总结堆排序——建堆 O(n)排序 O(nlogn)整体时间复杂度 O(nlogn)空间复杂度 O(1)是不稳定的原地排序算法。八、经典应用Top-K 问题8.1问题场景求海量数据中前 K 个最大或最小的元素数据量太大无法全部加载到内存排序这时候堆就是最优解。方法先取前k个数据进行建堆遍历剩下n-k个数据跟堆顶进行比较找最大的前k个数据建小堆比堆顶数据大就和堆顶数据交换找最小的前k个数据建大堆比堆顶数据小就和堆顶数据交换。8.2代码实现文件读取版优势不需要把全部数据加载到内存只需要维护大小为 K 的堆空间复杂度 O(K)时间复杂度 O(nlogK)非常适合海量数据场景。九、总结1. 堆是完全二叉树的顺序存储实现核心是父子下标公式和两个调整算法2. 向上调整对应入堆向下调整对应出堆、建堆、堆排序是最核心的操作3. 堆排序是原地排序升序建大堆、降序建小堆时间复杂度稳定 O(nlogn)4. Top-K 是堆的经典应用求前 K 大建小堆、求前 K 小建大堆是海量数据场景的最优解