目录一、堆的基础概念什么是堆堆的关键特性二、堆的 C 语言实现完整代码解析2.1 头文件Heap.h定义结构体 函数声明2.2 源文件Heap.c实现堆的所有核心操作1. 基础辅助函数Swap交换两个元素2. 堆的初始化与销毁HPInit HPDestroy3. 上浮调整AdjustUP插入数据的核心4. 向堆中插入数据HPPush5. 下沉调整AdjustDown删除 / 建堆的核心6. 从堆中删除数据HPPop仅删除堆顶7. 堆的基础查询操作HPTop HPEmpty2.3 测试文件Test.c验证堆的功能 堆排序实现1. 堆的基础功能测试TestHeap12. 堆排序实现HeapSort TestHeap2三、小根堆转大根堆只需修改 2 处代码四、堆的核心应用场景五、总结堆Heap是数据结构中一种特殊的完全二叉树它不仅能高效实现优先队列还是堆排序的核心基础在 TopK 问题、任务调度等场景中应用广泛。本文将从堆的基础概念出发结合完整的 C 语言代码实现一步步讲透堆的初始化、插入、删除、堆排序等核心操作全程通俗易懂新手也能轻松掌握一、堆的基础概念什么是堆堆是一颗完全二叉树且满足堆的性质根据节点值的大小关系堆分为两种类型我们本文主要实现小根堆文末会说明大根堆的修改方法小根堆树中每个父节点的值 ≤ 其左右孩子节点的值堆顶根节点是整个堆的最小值大根堆树中每个父节点的值 ≥ 其左右孩子节点的值堆顶根节点是整个堆的最大值。堆的关键特性堆的物理存储实际开发中堆并非用二叉链表存储而是用数组顺序存储利用完全二叉树的节点下标关系实现父子节点的快速访问对于数组中下标为parent的父节点左孩子下标为2*parent1右孩子下标为2*parent2对于数组中下标为child的孩子节点父节点下标为(child-1)/2整数除法自动向下取整。堆的核心操作上浮调整AdjustUP和下沉调整AdjustDown这两个操作是实现堆插入、删除、建堆的基础。二、堆的 C 语言实现完整代码解析本文的堆实现基于小根堆代码分为三个文件Heap.h头文件声明结构体和函数、Heap.c源文件实现堆的核心操作、Test.c测试文件验证堆的功能和堆排序所有代码可直接编译运行注释清晰。2.1 头文件Heap.h定义结构体 函数声明首先定义堆的结构体和核心操作的函数声明约定堆的存储类型为int可通过HPDataType灵活修改堆的结构体包含三个核心成员存储数据的数组a、堆中有效元素个数size、数组的容量capacity。#pragma once #include stdio.h #include stdlib.h #includeassert.h #includestdbool.h // 定义堆的数据类型可按需修改如char、double typedef int HPDataType; // 堆的结构体定义顺序存储数组实现完全二叉树 typedef struct Heap { HPDataType* a; // 存储堆数据的数组 int size; // 堆中有效元素的个数 int capacity; // 数组的容量避免频繁扩容 }HP; // 堆的核心操作函数声明 void HPInit(HP* php); // 初始化堆 void HPDestroy(HP* php); // 销毁堆释放内存 void HPPush(HP* php, HPDataType data);// 向堆中插入数据 void AdjustUP(HPDataType* a, int child);// 上浮调整插入用 void Swap(HPDataType* p1, HPDataType* p2);// 交换两个元素辅助函数 void AdjustDown(HPDataType* a, int n, int parent);// 下沉调整删除/建堆用 void HPPop(HP* php); // 从堆中删除数据仅删除堆顶 HPDataType HPTop(HP* php); // 获取堆顶数据 bool HPEmpty(HP* php); // 判断堆是否为空2.2 源文件Heap.c实现堆的所有核心操作这是堆实现的核心包含初始化、销毁、插入、删除、上浮、下沉等所有操作每个函数都做了严格的断言校验避免空指针、越界等问题同时实现了数组的自动扩容。1. 基础辅助函数Swap交换两个元素堆的调整过程中需要频繁交换父子节点的值封装成通用函数提高代码复用性。void Swap(HPDataType* p1, HPDataType* p2) { HPDataType temp *p1; *p1 *p2; *p2 temp; }2. 堆的初始化与销毁HPInit HPDestroy初始化将数组置空有效元素个数和容量初始化为 0避免野指针销毁释放数组的动态内存再将所有成员置空防止内存泄漏。// 初始化堆 void HPInit(HP* php) { assert(php! NULL); // 断言避免传入空指针 php-a NULL; php-size 0; php-capacity 0; } // 销毁堆 void HPDestroy(HP* php) { assert(php! NULL); free(php-a); // 释放动态分配的数组内存 // 置空避免野指针 php-a NULL; php-size 0; php-capacity0; }3. 上浮调整AdjustUP插入数据的核心作用向堆中插入新元素后新元素放在数组末尾完全二叉树的最后一个节点此时可能破坏堆的性质需要通过上浮调整让新元素找到自己的正确位置恢复堆的性质。核心逻辑小根堆根据孩子节点下标计算父节点下标比较孩子节点和父节点的值若孩子节点更小交换两者将父节点作为新的孩子节点重复上述步骤直到孩子节点成为根节点下标为 0或满足堆的性质。void AdjustUP(HPDataType* a, int child) { int parent (child - 1) / 2; // 孩子找父节点的公式 while (child 0) // child0表示到根节点停止调整 { // 小根堆孩子父节点交换大根堆改为即可 if (a[child] a[parent]) { Swap(a[child], a[parent]); // 更新孩子和父节点继续向上调整 child parent; parent (child - 1) / 2; } else { break; // 满足堆的性质直接退出 } } }4. 向堆中插入数据HPPush核心步骤检查容量若有效元素个数等于容量进行数组扩容初始容量 4后续翻倍插入元素将新元素放在数组末尾php-a[php-size]有效元素个数 1上浮调整调用AdjustUP让新元素找到正确位置恢复堆的性质。void HPPush(HP* php, HPDataType data) { assert(php! NULL); // 容量不足扩容初始4后续翻倍 if (php-size php-capacity) { int newcapacity php-capacity 0 ? 4: php-capacity * 2; HPDataType* temp (HPDataType*)realloc(php-a, newcapacity * sizeof(HPDataType)); if (temp NULL) // 扩容失败报错并退出 { perror(realloc failed); exit(1); } php-a temp; php-capacity newcapacity; } // 插入新元素到数组末尾 php-a[php-size] data; php-size; // 上浮调整恢复堆的性质 AdjustUP(php-a, php-size - 1); }5. 下沉调整AdjustDown删除 / 建堆的核心作用删除堆顶元素或建堆时堆的性质被破坏需要通过下沉调整让根节点或指定节点向下移动找到自己的正确位置恢复堆的性质。核心逻辑小根堆根据父节点下标计算左孩子下标默认左孩子为更小的孩子找到左右孩子中更小的那个右孩子存在时才比较比较父节点和最小孩子节点的值若父节点更大交换两者将最小孩子节点作为新的父节点重复上述步骤直到孩子节点超出堆的范围到达叶子节点或满足堆的性质。void AdjustDown(HPDataType* a, int n, int parent) { assert(a ! NULL); // 父节点找左孩子的公式默认左孩子更小 int child 2 * parent 1; while (child n) // childn表示到达叶子节点停止调整 { // 找到左右孩子中更小的那个右孩子存在才比较 if (child 1 n a[child 1] a[child]) { child; // 右孩子更小切换到右孩子 } // 小根堆孩子父节点交换大根堆改为即可 if (a[child] a[parent]) { Swap(a[child], a[parent]); // 更新父节点和孩子节点继续向下调整 parent child; child 2 * parent 1; } else { break; // 满足堆的性质直接退出 } } }6. 从堆中删除数据HPPop仅删除堆顶堆的删除操作仅支持删除堆顶元素堆的核心特性若删除任意节点需额外处理核心步骤交换堆顶和堆的最后一个元素将堆顶元素移到数组末尾方便删除有效元素个数 - 1逻辑删除无需真正修改数组后续扩容 / 插入会覆盖下沉调整对新的堆顶元素调用AdjustDown恢复堆的性质。void HPPop(HP* php) { assert(php ! NULL); assert(php-size); // 断言堆为空时不能删除 // 交换堆顶和最后一个元素 Swap(php-a[0], php-a[php-size - 1]); // 逻辑删除最后一个元素原堆顶 php-size--; // 下沉调整新的堆顶恢复堆的性质 AdjustDown(php-a, php-size,0); }7. 堆的基础查询操作HPTop HPEmptyHPTop获取堆顶元素小根堆为最小值大根堆为最大值需断言堆非空HPEmpty判断堆是否为空通过有效元素个数size是否为 0 实现。// 获取堆顶数据 HPDataType HPTop(HP* php) { assert(php ! NULL); assert(php-size 0); // 堆为空不能获取堆顶 return php-a[0]; } // 判断堆是否为空 bool HPEmpty(HP* php) { assert(php ! NULL); return php-size 0; }2.3 测试文件Test.c验证堆的功能 堆排序实现测试文件包含两个核心测试TestHeap1验证堆的插入、删除、获取堆顶等基础功能TestHeap2实现堆排序并验证主函数可直接调用测试。1. 堆的基础功能测试TestHeap1向堆中插入 10 个随机整数然后循环 5 次获取并删除堆顶元素小根堆的堆顶始终是当前堆的最小值因此输出结果为0 1 2 3 4。#include Heap.h // 测试堆的基础功能插入、删除、获取堆顶 void TestHeap1() { int a[10] { 5,3,8,1,6,7,2,4,9,0 }; HP hp; HPInit(hp); // 向堆中插入所有元素 for (int i 0; i sizeof(a) / sizeof(a[0]); i) { HPPush(hp, a[i]); } // 循环5次获取堆顶并删除 int k 5; while (!HPEmpty(hp)k--) { printf(%d , HPTop(hp)); // 输出堆顶最小值 HPPop(hp); // 删除堆顶 } HPDestroy(hp); // 销毁堆释放内存 }2. 堆排序实现HeapSort TestHeap2堆排序是堆的经典应用时间复杂度为O(nlogn)空间复杂度为O(1)原地排序核心思路基于小根堆实现升序排序大根堆可实现降序排序建堆将无序数组构建为小根堆建堆的时间复杂度为O(n)建堆从最后一个非叶子节点开始下标为(n-1-1)/2从后往前依次调用AdjustDown最后一个非叶子节点完全二叉树中最后一个节点的父节点就是最后一个非叶子节点。排序循环将堆顶最小值与堆的最后一个元素交换然后对新的堆顶进行下沉调整直到堆的有效元素个数为 1交换堆顶和最后一个元素将最小值放到数组末尾成为有序部分下沉调整缩小堆的范围end--对新堆顶调整恢复堆的性质。// 堆排序基于小根堆实现升序排序 void HeapSort(int *a, int n) { // 步骤1建堆从最后一个非叶子节点开始从后往前下沉调整 for (int i (n-1-1)/2; i 0; i--) { AdjustDown(a,n,i); } // 步骤2排序 int end n - 1; // end表示堆的最后一个元素下标 while (end 0) { Swap(a[0], a[end]); // 交换堆顶和最后一个元素最小值归位 AdjustDown(a,end,0 ); // 对新堆顶下沉调整堆的范围缩小为[0, end-1] --end; // 缩小堆的范围 } } // 测试堆排序 void TestHeap2() { int a[] { 500,3,8,1,6,2,4 }; HeapSort(a, sizeof(a) / sizeof(a[0])); // 输出排序结果1 2 3 4 6 8 500 for (int i 0; i sizeof(a) / sizeof(a[0]); i) { printf(%d , a[i]); } } // 主函数调用测试 int main() { //TestHeap1(); // 测试堆的基础功能 TestHeap2(); // 测试堆排序 return 0; }三、小根堆转大根堆只需修改 2 处代码本文实现的是小根堆若需要实现大根堆堆顶为最大值可实现降序堆排序只需修改AdjustUP和AdjustDown中的比较条件将改为即可其余代码完全不变上浮调整AdjustUP// 大根堆孩子父节点交换 if (a[child] a[parent])下沉调整AdjustDown// 大根堆找到左右孩子中更大的那个 if (child 1 n a[child 1] a[child]) // 大根堆孩子父节点交换 if (a[child] a[parent])修改后TestHeap1的输出会变为9 8 7 6 5堆顶始终是最大值堆排序HeapSort会实现降序排序。四、堆的核心应用场景堆作为高效的优先队列实现在实际开发中应用广泛主要包括堆排序时间复杂度O(nlogn)原地排序适用于大数据量的排序场景TopK 问题找一组数据中最大 / 最小的 k 个元素如找销量前 10 的商品、分数最高的 5 个学生用小根堆 / 大根堆实现时间复杂度O(nlogk)比直接排序更高效任务调度如操作系统的进程调度、任务队列的优先级执行优先级高的任务放在堆顶优先执行图论算法如 Dijkstra 最短路径算法、Prim 最小生成树算法用堆优化后可将时间复杂度从O(n²)降为O(nlogn)。五、总结堆是完全二叉树分为小根堆和大根堆物理上用数组存储利用父子节点的下标公式实现快速访问堆的核心操作是上浮调整AdjustUP和下沉调整AdjustDown插入用上浮删除 / 建堆用下沉堆的插入和删除操作时间复杂度均为O(logn)建堆时间复杂度为O(n)堆排序时间复杂度为O(nlogn)小根堆和大根堆的转换仅需修改比较条件代码复用性高堆的核心优势是高效获取最值堆顶广泛应用于 TopK、任务调度、堆排序等场景。
数据结构-堆学习
目录一、堆的基础概念什么是堆堆的关键特性二、堆的 C 语言实现完整代码解析2.1 头文件Heap.h定义结构体 函数声明2.2 源文件Heap.c实现堆的所有核心操作1. 基础辅助函数Swap交换两个元素2. 堆的初始化与销毁HPInit HPDestroy3. 上浮调整AdjustUP插入数据的核心4. 向堆中插入数据HPPush5. 下沉调整AdjustDown删除 / 建堆的核心6. 从堆中删除数据HPPop仅删除堆顶7. 堆的基础查询操作HPTop HPEmpty2.3 测试文件Test.c验证堆的功能 堆排序实现1. 堆的基础功能测试TestHeap12. 堆排序实现HeapSort TestHeap2三、小根堆转大根堆只需修改 2 处代码四、堆的核心应用场景五、总结堆Heap是数据结构中一种特殊的完全二叉树它不仅能高效实现优先队列还是堆排序的核心基础在 TopK 问题、任务调度等场景中应用广泛。本文将从堆的基础概念出发结合完整的 C 语言代码实现一步步讲透堆的初始化、插入、删除、堆排序等核心操作全程通俗易懂新手也能轻松掌握一、堆的基础概念什么是堆堆是一颗完全二叉树且满足堆的性质根据节点值的大小关系堆分为两种类型我们本文主要实现小根堆文末会说明大根堆的修改方法小根堆树中每个父节点的值 ≤ 其左右孩子节点的值堆顶根节点是整个堆的最小值大根堆树中每个父节点的值 ≥ 其左右孩子节点的值堆顶根节点是整个堆的最大值。堆的关键特性堆的物理存储实际开发中堆并非用二叉链表存储而是用数组顺序存储利用完全二叉树的节点下标关系实现父子节点的快速访问对于数组中下标为parent的父节点左孩子下标为2*parent1右孩子下标为2*parent2对于数组中下标为child的孩子节点父节点下标为(child-1)/2整数除法自动向下取整。堆的核心操作上浮调整AdjustUP和下沉调整AdjustDown这两个操作是实现堆插入、删除、建堆的基础。二、堆的 C 语言实现完整代码解析本文的堆实现基于小根堆代码分为三个文件Heap.h头文件声明结构体和函数、Heap.c源文件实现堆的核心操作、Test.c测试文件验证堆的功能和堆排序所有代码可直接编译运行注释清晰。2.1 头文件Heap.h定义结构体 函数声明首先定义堆的结构体和核心操作的函数声明约定堆的存储类型为int可通过HPDataType灵活修改堆的结构体包含三个核心成员存储数据的数组a、堆中有效元素个数size、数组的容量capacity。#pragma once #include stdio.h #include stdlib.h #includeassert.h #includestdbool.h // 定义堆的数据类型可按需修改如char、double typedef int HPDataType; // 堆的结构体定义顺序存储数组实现完全二叉树 typedef struct Heap { HPDataType* a; // 存储堆数据的数组 int size; // 堆中有效元素的个数 int capacity; // 数组的容量避免频繁扩容 }HP; // 堆的核心操作函数声明 void HPInit(HP* php); // 初始化堆 void HPDestroy(HP* php); // 销毁堆释放内存 void HPPush(HP* php, HPDataType data);// 向堆中插入数据 void AdjustUP(HPDataType* a, int child);// 上浮调整插入用 void Swap(HPDataType* p1, HPDataType* p2);// 交换两个元素辅助函数 void AdjustDown(HPDataType* a, int n, int parent);// 下沉调整删除/建堆用 void HPPop(HP* php); // 从堆中删除数据仅删除堆顶 HPDataType HPTop(HP* php); // 获取堆顶数据 bool HPEmpty(HP* php); // 判断堆是否为空2.2 源文件Heap.c实现堆的所有核心操作这是堆实现的核心包含初始化、销毁、插入、删除、上浮、下沉等所有操作每个函数都做了严格的断言校验避免空指针、越界等问题同时实现了数组的自动扩容。1. 基础辅助函数Swap交换两个元素堆的调整过程中需要频繁交换父子节点的值封装成通用函数提高代码复用性。void Swap(HPDataType* p1, HPDataType* p2) { HPDataType temp *p1; *p1 *p2; *p2 temp; }2. 堆的初始化与销毁HPInit HPDestroy初始化将数组置空有效元素个数和容量初始化为 0避免野指针销毁释放数组的动态内存再将所有成员置空防止内存泄漏。// 初始化堆 void HPInit(HP* php) { assert(php! NULL); // 断言避免传入空指针 php-a NULL; php-size 0; php-capacity 0; } // 销毁堆 void HPDestroy(HP* php) { assert(php! NULL); free(php-a); // 释放动态分配的数组内存 // 置空避免野指针 php-a NULL; php-size 0; php-capacity0; }3. 上浮调整AdjustUP插入数据的核心作用向堆中插入新元素后新元素放在数组末尾完全二叉树的最后一个节点此时可能破坏堆的性质需要通过上浮调整让新元素找到自己的正确位置恢复堆的性质。核心逻辑小根堆根据孩子节点下标计算父节点下标比较孩子节点和父节点的值若孩子节点更小交换两者将父节点作为新的孩子节点重复上述步骤直到孩子节点成为根节点下标为 0或满足堆的性质。void AdjustUP(HPDataType* a, int child) { int parent (child - 1) / 2; // 孩子找父节点的公式 while (child 0) // child0表示到根节点停止调整 { // 小根堆孩子父节点交换大根堆改为即可 if (a[child] a[parent]) { Swap(a[child], a[parent]); // 更新孩子和父节点继续向上调整 child parent; parent (child - 1) / 2; } else { break; // 满足堆的性质直接退出 } } }4. 向堆中插入数据HPPush核心步骤检查容量若有效元素个数等于容量进行数组扩容初始容量 4后续翻倍插入元素将新元素放在数组末尾php-a[php-size]有效元素个数 1上浮调整调用AdjustUP让新元素找到正确位置恢复堆的性质。void HPPush(HP* php, HPDataType data) { assert(php! NULL); // 容量不足扩容初始4后续翻倍 if (php-size php-capacity) { int newcapacity php-capacity 0 ? 4: php-capacity * 2; HPDataType* temp (HPDataType*)realloc(php-a, newcapacity * sizeof(HPDataType)); if (temp NULL) // 扩容失败报错并退出 { perror(realloc failed); exit(1); } php-a temp; php-capacity newcapacity; } // 插入新元素到数组末尾 php-a[php-size] data; php-size; // 上浮调整恢复堆的性质 AdjustUP(php-a, php-size - 1); }5. 下沉调整AdjustDown删除 / 建堆的核心作用删除堆顶元素或建堆时堆的性质被破坏需要通过下沉调整让根节点或指定节点向下移动找到自己的正确位置恢复堆的性质。核心逻辑小根堆根据父节点下标计算左孩子下标默认左孩子为更小的孩子找到左右孩子中更小的那个右孩子存在时才比较比较父节点和最小孩子节点的值若父节点更大交换两者将最小孩子节点作为新的父节点重复上述步骤直到孩子节点超出堆的范围到达叶子节点或满足堆的性质。void AdjustDown(HPDataType* a, int n, int parent) { assert(a ! NULL); // 父节点找左孩子的公式默认左孩子更小 int child 2 * parent 1; while (child n) // childn表示到达叶子节点停止调整 { // 找到左右孩子中更小的那个右孩子存在才比较 if (child 1 n a[child 1] a[child]) { child; // 右孩子更小切换到右孩子 } // 小根堆孩子父节点交换大根堆改为即可 if (a[child] a[parent]) { Swap(a[child], a[parent]); // 更新父节点和孩子节点继续向下调整 parent child; child 2 * parent 1; } else { break; // 满足堆的性质直接退出 } } }6. 从堆中删除数据HPPop仅删除堆顶堆的删除操作仅支持删除堆顶元素堆的核心特性若删除任意节点需额外处理核心步骤交换堆顶和堆的最后一个元素将堆顶元素移到数组末尾方便删除有效元素个数 - 1逻辑删除无需真正修改数组后续扩容 / 插入会覆盖下沉调整对新的堆顶元素调用AdjustDown恢复堆的性质。void HPPop(HP* php) { assert(php ! NULL); assert(php-size); // 断言堆为空时不能删除 // 交换堆顶和最后一个元素 Swap(php-a[0], php-a[php-size - 1]); // 逻辑删除最后一个元素原堆顶 php-size--; // 下沉调整新的堆顶恢复堆的性质 AdjustDown(php-a, php-size,0); }7. 堆的基础查询操作HPTop HPEmptyHPTop获取堆顶元素小根堆为最小值大根堆为最大值需断言堆非空HPEmpty判断堆是否为空通过有效元素个数size是否为 0 实现。// 获取堆顶数据 HPDataType HPTop(HP* php) { assert(php ! NULL); assert(php-size 0); // 堆为空不能获取堆顶 return php-a[0]; } // 判断堆是否为空 bool HPEmpty(HP* php) { assert(php ! NULL); return php-size 0; }2.3 测试文件Test.c验证堆的功能 堆排序实现测试文件包含两个核心测试TestHeap1验证堆的插入、删除、获取堆顶等基础功能TestHeap2实现堆排序并验证主函数可直接调用测试。1. 堆的基础功能测试TestHeap1向堆中插入 10 个随机整数然后循环 5 次获取并删除堆顶元素小根堆的堆顶始终是当前堆的最小值因此输出结果为0 1 2 3 4。#include Heap.h // 测试堆的基础功能插入、删除、获取堆顶 void TestHeap1() { int a[10] { 5,3,8,1,6,7,2,4,9,0 }; HP hp; HPInit(hp); // 向堆中插入所有元素 for (int i 0; i sizeof(a) / sizeof(a[0]); i) { HPPush(hp, a[i]); } // 循环5次获取堆顶并删除 int k 5; while (!HPEmpty(hp)k--) { printf(%d , HPTop(hp)); // 输出堆顶最小值 HPPop(hp); // 删除堆顶 } HPDestroy(hp); // 销毁堆释放内存 }2. 堆排序实现HeapSort TestHeap2堆排序是堆的经典应用时间复杂度为O(nlogn)空间复杂度为O(1)原地排序核心思路基于小根堆实现升序排序大根堆可实现降序排序建堆将无序数组构建为小根堆建堆的时间复杂度为O(n)建堆从最后一个非叶子节点开始下标为(n-1-1)/2从后往前依次调用AdjustDown最后一个非叶子节点完全二叉树中最后一个节点的父节点就是最后一个非叶子节点。排序循环将堆顶最小值与堆的最后一个元素交换然后对新的堆顶进行下沉调整直到堆的有效元素个数为 1交换堆顶和最后一个元素将最小值放到数组末尾成为有序部分下沉调整缩小堆的范围end--对新堆顶调整恢复堆的性质。// 堆排序基于小根堆实现升序排序 void HeapSort(int *a, int n) { // 步骤1建堆从最后一个非叶子节点开始从后往前下沉调整 for (int i (n-1-1)/2; i 0; i--) { AdjustDown(a,n,i); } // 步骤2排序 int end n - 1; // end表示堆的最后一个元素下标 while (end 0) { Swap(a[0], a[end]); // 交换堆顶和最后一个元素最小值归位 AdjustDown(a,end,0 ); // 对新堆顶下沉调整堆的范围缩小为[0, end-1] --end; // 缩小堆的范围 } } // 测试堆排序 void TestHeap2() { int a[] { 500,3,8,1,6,2,4 }; HeapSort(a, sizeof(a) / sizeof(a[0])); // 输出排序结果1 2 3 4 6 8 500 for (int i 0; i sizeof(a) / sizeof(a[0]); i) { printf(%d , a[i]); } } // 主函数调用测试 int main() { //TestHeap1(); // 测试堆的基础功能 TestHeap2(); // 测试堆排序 return 0; }三、小根堆转大根堆只需修改 2 处代码本文实现的是小根堆若需要实现大根堆堆顶为最大值可实现降序堆排序只需修改AdjustUP和AdjustDown中的比较条件将改为即可其余代码完全不变上浮调整AdjustUP// 大根堆孩子父节点交换 if (a[child] a[parent])下沉调整AdjustDown// 大根堆找到左右孩子中更大的那个 if (child 1 n a[child 1] a[child]) // 大根堆孩子父节点交换 if (a[child] a[parent])修改后TestHeap1的输出会变为9 8 7 6 5堆顶始终是最大值堆排序HeapSort会实现降序排序。四、堆的核心应用场景堆作为高效的优先队列实现在实际开发中应用广泛主要包括堆排序时间复杂度O(nlogn)原地排序适用于大数据量的排序场景TopK 问题找一组数据中最大 / 最小的 k 个元素如找销量前 10 的商品、分数最高的 5 个学生用小根堆 / 大根堆实现时间复杂度O(nlogk)比直接排序更高效任务调度如操作系统的进程调度、任务队列的优先级执行优先级高的任务放在堆顶优先执行图论算法如 Dijkstra 最短路径算法、Prim 最小生成树算法用堆优化后可将时间复杂度从O(n²)降为O(nlogn)。五、总结堆是完全二叉树分为小根堆和大根堆物理上用数组存储利用父子节点的下标公式实现快速访问堆的核心操作是上浮调整AdjustUP和下沉调整AdjustDown插入用上浮删除 / 建堆用下沉堆的插入和删除操作时间复杂度均为O(logn)建堆时间复杂度为O(n)堆排序时间复杂度为O(nlogn)小根堆和大根堆的转换仅需修改比较条件代码复用性高堆的核心优势是高效获取最值堆顶广泛应用于 TopK、任务调度、堆排序等场景。
