数据结构堆 优先队列的概念、实现及应用场景

博主名称_Doubletful大家好欢迎来到Doubletful的博客博主的GitHub Go to git_hub数据结构专栏路漫漫其修远兮吾将上下而求索文章目录前言一、概念1.二叉树概念2.堆的概念3.堆的数组表示4.为何必须是完全二叉树二、代码实现1.准备2.头文件内容总览3.初始化堆4.判断空间容量5.添加数据6.向上调整算法7.删除数据8.向下调整算法9.获取堆顶元素10.判断是否为空11.销毁堆三、应用场景1.堆排序1.1.建堆1.1.1.大小堆选择1.1.2.向上调整建堆1.1.3.向下调整建堆1.1.4.方法二时间复杂度分析1.2.排序循环2.TopK问题2.1.结论二代价解释2.2.经典解法介绍2.3.大小堆选择2.4.创建带有十万个随机数的文件2.5.在电脑中找到数据文件2.6.TopK代码实现3.其他应用场景简介四、总结1.一份测试代码2.整体总结前言——在计算机科学中堆Heap是一种极其基础而又强大的数据结构本文将从二叉树的基础出发逐步深入堆的核心概念剖析其实现细节并探讨其在实际工程中的典型应用。文章将使用C语言实现基础数据结构——堆主要内容包括1.使用头文件声明、源文件定义的形式实现2.从二叉树到堆的概念实现原理与操作接口的详解3.提供完整的代码示例、图例和实际应用场景分析一、概念1.二叉树概念堆本质上是一种特殊的完全二叉树。因此在理解堆之前我们需要先回顾二叉树的一些基本性质二叉树每个节点最多有两个子节点的树结构。满二叉树二叉树的每一层的节点数都达到最大值则称其为满二叉树。完全二叉树前 h - 1 层的节点数都达到最大值最后一层不满但从左到右必须是连续的。堆要求其底层结构必须是一棵完全二叉树这一限制使得堆可以用数组高效存储而无需使用指针。如果对“要求其底层结构必须是一棵完全二叉树”抱有疑问请移至下文阅读。2.堆的概念堆是一种满足以下两种性质之一的完全二叉树大根堆Max Heap每个节点的值都严格大于或等于其子节点的值。根节点是全局最大值。小根堆Min Heap每个节点的值都严格小于或等于其子节点的值。根节点是全局最小值。注意堆只规定了父节点与子节点的关系但不规定左右子节点之间的大小关系换言之堆限制上下而不在意左右大小关系。那么我们应该用什么内置结构来从逻辑上实现堆呢数组并且使用结构体封装其属性元素个数与容量与顺序表的物理结构一致因此实现更注重于逻辑层面。3.堆的数组表示在数组中使用下标位表示父节点与子节点的关系具体性质如下父亲的下标为 i 时左孩子的下标为 2 * i 1右孩子的下标为 2 * i 2左孩子在数组中的下标都为奇数右孩子在数组中的下标都为偶数。当任意孩子在数组中的下标为 j 时其父亲在数组中的下标为 (j - 1) / 2无论是左孩子或右孩子都通用因为计算向下取整整型性质。解释通过右孩子找到其父节点的计算为 (2 * i 2) - 1 等于 (2 * i 1) / 2 等于 i 0.5 后向下取整等于 i找到对应父节点下标。数据结构堆的物理结构与逻辑结构示例图4.为何必须是完全二叉树当二叉树出现比较极端的情况时使用数组存储会很浪费空间☄️在实际应用场景下这种情况不仅会非常常见并且数据量级也将巨额增长所以非满二叉树或完全二叉树并不适合使用数组存储。二、代码实现1.准备前置知识assert()函数介绍C语言标准库中的调试宏用于在程序运行时检查条件是否成立。若条件为假0则输出错误信息文件、行号、表达式并调用 abort()终止程序若条件为真非0则无动作。常用于捕捉“不可能发生”的逻辑错误、验证函数前置条件等。perror()函数介绍C语言标准库函数用于打印错误信息。调用格式perror(“前缀字符串”)输出格式为“前缀字符串错误原因\n”常用于系统调用或库函数失败后快速定位错误原因。exit()函数介绍C语言标准库函数用于正常终止程序。刷新所有输出缓冲区、关闭已打开的流。将退出状态码返回给操作系统0or EXIT_SUCCESS表示成功-1or EXIT_FAILURE表示失败。布尔值C语言并不自带布尔值作为内置数据类型使用需引入标准库stdbool.h交换函数C语言并不自带交换函数需手动实现其中的数据类型 HPDataType 为手动定义的堆存储数据类型。voidSwap(HPDataType*p1,HPDataType*p2){HPDataType tmp*p1;*p1*p2;*p2tmp;}2.头文件内容总览注代码部分如果直接复制不能成功运行请将所有中文前的#替换为//#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#includestdbool.h#includetime.h#TopK问题生成随机数据需要typedefintHPDataType;typedefstructHeap{HPDataType*arr;#存储堆节点的数组intsize;intcapacity;}HP;#初始化堆voidHPInit(HP*php);#添加数据voidHPPush(HP*php,HPDataType x);#删除数据voidHPPop(HP*php);#获取堆顶元素 HPDataTypeHPTop(HP*php);#判断是否为空 boolHPEmpty(HP*php);#销毁堆voidHPDestroy(HP*php);初始化与销毁返回堆顶元素和判空添加与删除数据看起来与之前的数据结构实现并无不同但其中有两个隐藏的核心辅助函数向上调整元素上浮与向下调整元素下沉分别在添加与删除处讲解。注实现部分皆使用小根堆演示大根堆只需修改部分代码的判断条件即可。3.初始化堆voidHPInit(HP*php){assert(php);php-arrNULL;php-sizephp-capacity0;}传入堆并断言传入的指针不为 NULL。初始化作为堆载体的数组并将属性容量和大小置零。4.判断空间容量voidHPCheckCapacity(HP*php){if(php-sizephp-capacity){intnewcapacity(php-capacity0?4:php-capacity*2);HPDataType*tmp(HPDataType*)realloc(php-arr,newcapacity*sizeof(HPDataType));if(tmpNULL){perror(realloc fail);exit(1);}php-arrtmp;php-capacitynewcapacity;}}当第一次扩容时初始化容量为4否则扩容为当前容量的二倍扩容后需判断是否扩容成功失败返回提示信息后退出程序成功时再执行更新操作。5.添加数据voidHPPush(HP*php,HPDataType x){assert(php);HPCheckCapacity(php);#添加 php-arr[php-size]x;#向上调整插入数据ADJustUp(php-arr,php-size-1);}传入堆并断言传入的指针不为 NULL。我们选择在堆尾插入数据时会产生一个问题新插入的数据可能违反堆的规则大根堆情况下比父节点大或小根堆情况下比父节点小此时需要不断与其对应父节点交换直到恢复堆序。核心辅助函数向上调整算法 ADJustUp 负责添加时的交换下面详细介绍。6.向上调整算法voidADJustUp(HPDataType*arr,intchild){#孩子对应的父亲下标intparent(child-1)/2;#父亲比孩子大时交换(小堆情况)while(arr[parent]arr[child]){Swap(arr[parent],arr[child]);#依次比较祖先父亲与孩子的关系 childparent;parent(child-1)/2;}}向上调整函数的参数为表示堆的数组及新插入数据的下标。首先计算新插入数据(以下简称 x)的父节点下标其次通过判断确定是否符合堆的规则不符合就交换并继续计算交换位置后的 x 对应的父节点下标直到符合堆的规则为止。注当 child 等于 0 时减 1 除 2 的计算结果为 -0.5根据整型性质得出对应的 parent 也为 0必然因为 arr[parent] 不大于 arr[child] 自然终止因此不会越界访问最多将 x 调整到根节点终止。7.删除数据voidHPPop(HP*php){assert(phpphp-size);#删除 #交换堆顶与堆底的数据Swap(php-arr,php-arr[php-size-1]);php-size--;#删除当前堆底数据 #向下调整数据ADJustDown(php-arr,php-size,0);}传入堆断言传入指针不为 NULL 且堆中元素个数不为0。删除堆底数据无实际意义因此改为每次删除堆顶的值方式为将堆顶的值与堆底的值交换删除当前堆底的值即原根结点的值此时堆顶可能违反堆序仍需不断与较大的子节点或较小的子节点交换直到恢复堆序。核心辅助函数向下调整算法 ADJustDown 负责删除时的交换下面详细介绍。8.向下调整算法voidADJustDown(HPDataType*arr,intn,intparent){#假设左孩子比右孩子小intchildparent*21;#最多交换到叶节点防止越界访问(小堆情况)while(childn){#右孩子比左孩子小判断右孩子是否存在防止越界访问if(child1narr[child1]arr[child])child;#孩子比父亲小时交换if(arr[child]arr[parent]){Swap(arr[child],arr[parent]);#依次比较子孙父亲与孩子的关系 parentchild;childparent*21;}else{break;}}}向下调整函数的参数为表示堆的数组数组大小及堆顶下标。由于是向下调整需明确堆底的边界防止越界因此传入数组大小。先计算出左孩子的下标位并在循环中取左右孩子的较小值用于交换此处需注意保证右孩子存在即 child 1 n。✨为什么取左右孩子的较小值在小堆情况时设左孩子比右孩子大且父节点的值大于左孩子需交换那么在将父节点与左孩子交换后新父节点的值依然不符合堆规比右孩子大所以需取左右孩子的较小值使其在交换后完全符合堆的规则。凭此我们找到了正确的交换子节点之后的操作与向上调整算法大致相同都是先判断再交换最后继续计算交换位置后对应的子节点下标直到子节点比父节点大时或遍历到最后的叶节点时终止。9.获取堆顶元素HPDataTypeHPTop(HP*php){assert(phpphp-size);returnphp-arr[0];}传入堆断言传入指针不为 NULL 且堆中元素个数不为0。直接根据下标返回堆顶元素即可。10.判断是否为空boolHPEmpty(HP*php){assert(php);returnphp-size0;}传入堆并断言传入的指针不为 NULL。数组下标的一个性质各自下标位等同于其位置前的元素个数——因此通过 size 当前指向的下标位判断堆是否为空为空返回 true否则返回 false。11.销毁堆voidHPDestroy(HP*php){assert(php);free(php-arr);php-arrNULL;php-sizephp-capacity0;}传入堆并断言传入的指针不为 NULL。释放开辟的动态空间并将指针初始化初始化大小和容量。三、应用场景堆的设计初衷是为了高效获取极值因此它的应用几乎都围绕这一特性展开。1.堆排序堆排序是堆结构最经典的应用之一它充分利用了“堆顶必为极值”这一特性实现了一种原地且最坏情况下时间复杂度为 O(N*logN) 的排序算法。优点空间复杂度为O(1)最坏情况表现稳定不存在退化到 O(N²) 的风险。提问为什么空间复杂度为O(1)难道不需要创建数据结构堆吗答确实不需要因为数据结构堆本身就是用数组实现的并且被排序数组不遵循堆规问题也有解决办法使用核心辅助函数即可将被排序数组堆化。1.1.建堆1.1.1.大小堆选择首先需要明确一个易混淆的点若想得到升序序列应使用大根堆若想得到降序序列应使用小根堆。⚙️为什么堆排序的核心操作是将堆顶元素与堆末尾元素交换然后将末尾“切除固定”再对新的堆顶向下调整恢复堆序。使用大根堆时每次被切除并放到数组末尾的都是当前最大值因此数组从后往前依次被填满最大值最终整体呈升序。降序同理每次被固定到数组末尾的都是当前最小值。1.1.2.向上调整建堆#方法一向上调整建堆时间复杂度为O(N*logN)for(inti1;isize;i){AdjustUp(arr,i);}i 从 1 开始调整这意味着首先将 0 ~ 1 位调整为一个堆在此基础上逐渐拓展调整范围如同添加数据一样先将新值插入在堆末尾再使用向上调整算法使其符合堆规此种做法的时间复杂度为O(N*logN)。接下来重点介绍时间复杂度更优的方法二并且详解时间复杂度的数学推导。1.1.3.向下调整建堆#方法二向下调整建堆时间复杂度为O(N)for(inti(size-2)/2;i0;i--){ADJustDown(arr,size,i);}i 从最后一个节点的父亲开始调整最后一个节点下标为 size - 1这意味着开始向下调整的位置是最后一个叶结点的父节点即最后一个父节点。从该节点开始建堆随着 i 每次向前递减相当于每次在堆顶插入一个新值后将新值向下调整直到符合堆规。1.1.4.方法二时间复杂度分析从上至下看第一层有 20个节点最坏向下调整 h - 1 次第二层有 21个节点最坏向下调整 h - 2 次。从下至上看第 h - 1 层有 2h-2个节点最坏向下调整 1 次第 h - 2 层有 2h-3个节点最坏向下调整 2 次。由此可以得到式子并计算首先利用错位相减法化简等差乘等比的数列其次利用等差数列求和公式化简并将结果转换为以 N 表示的形式最后将得到的具体时间复杂度去除影响不大的项得到O(N)。1.2.排序循环#将数组排为降序时间复杂度为O(N*logN)intendsize-1;#每次将当前最小值交换到数组末尾while(end0){Swap(arr,arr[end]);#将被交换到根节点的值向下调整到合适位置(使数组仍是小堆)ADJustDown(arr,end,0);end--;}在建好小根堆后依次将当前根节点的极值交换到数组末尾end 负责控制交换的位置以便从后向前遍历数组和固定交换到数组末尾的极值终止条件为 end 位置无需进行交换操作时也就是当 end 遍历到根节点时。2.TopK问题⇒一句话解释TopK问题N 个数找最大或最小的前 K 个。这里的 K 通常远远小于 N例如从 1 亿条用户记录中找出积分最高的 10 名用户因此依现实情况得出结论一因堆顶必为极值的特性它天然适合解此类问题。结论二我们不可能为了找 10 个数据而开辟一个 1 亿数据量的数组并排序数据集在硬盘中存储需转入运行时内存。2.1.结论二代价解释所占内存过大用存储整型的情况计算共 4 × 109个字节所占内存约为 0.09GB看起来好像还能接受但如果存储的数据类型是双精度浮点数并且数据量级为 10 亿所占内存约为 1.8GB。绝大多数的应用程序所占内存共 20~30GB从总量对比来看很明显这一极小的功能并不配占有着如此高的内存占比此方法代价过大。因此这里只推荐一种简单又高效的方法解决TopK问题介绍如下。2.2.经典解法介绍创建数据量为 K 个的堆将数据一条一条喂给Ta无论数据总量多大堆里永远只存着当前最佳的 K 个“候选人”。2.3.大小堆选择求最大的 K 个元素维护一个小根堆根节点是堆中最小的元素每当新元素到来只要它比堆顶大就替换掉堆顶然后向下调整。这样堆里剩下的永远是最大的 K 个数据。求最小的 K 个元素维护一个大根堆根节点是堆中最大的元素每当新元素比堆顶小就替换掉堆顶剩下的永远是最小的 K 个数据。2.4.创建带有十万个随机数的文件voidCreateNData(){srand((unsignedint)time(NULL));FILE*finfopen(data.txt,w);if(finNULL){perror(fopen fail);return;}intn100000;for(inti0;in;i){intxrand()i;fprintf(fin,%d\n,x);}fclose(fin);}srand((unsigned int)time(NULL)) 的作用是使 rand 函数每次运行时生成的随机数不同下面将依次解释这几个函数的功能。rand()函数介绍用于生成随机数使用需要头文件 stdlib.h不需要参数返回值为一个伪随机数范围在 0~RAND_MAX其内部对一个叫种子的基准值进行运算生成随机数且 rand 函数的默认种子是1。srand()函数介绍srand 函数用于初始化随机数生成器(种子)需要一个变化的参数类型为无符号整型。time()函数介绍time 函数用于返回一个时间戳使用需要头文件 time.h可以接收一个参数返回值为一个时间戳时间戳是一个数字如果接收的参数为NULL就只返回时间戳。因此将 time 函数的返回值转为无符号整型传入 srand 函数就能使 rand 函数每次运行时生成的随机数不同。用写的方式打开文件判断是否打开成功失败返回错误信息并退出成功后继续使用 fprintf 函数以特定格式写入数据最后关闭文件流。注rand 函数能产生的不重复随机数只有三万多每次加 i 能减少重复量。2.5.在电脑中找到数据文件由于写操作会创建文件后写入且打开文件时的路径为当前目录下的相对路径因此可以直接在同级目录中找到数据文件 data.txt。2.6.TopK代码实现voidTest_TopK(){#创建数据CreateNData();intk0;scanf(%d,k);int*kheap(int*)malloc(sizeof(int)*k);if(kheapNULL){perror(malloc fail);exit(1);}#读取前k个数据 FILE*foutfopen(data.txt,r);for(inti0;ik;i){fscanf(fout,%d,kheap[i]);}#建堆for(inti(k-2)/2;i0;i--){ADJustDown(kheap,k,i);}#依次用堆顶数据比较文件的剩余数据intx0;while(fscanf(fout,%d,x)0){#剩余数据大于堆顶数据if(kheap[0]x){#替换堆顶数据并向下调整 kheap[0]x;ADJustDown(kheap,k,0);}}for(inti0;ik;i){printf(%d ,kheap[i]);}printf(\n);free(kheap);}动态接收想获取的数据个数 K创建堆空间后先从文件中读出 K 个数据到数组中并建堆再依次从文件中将每个数据读出并与堆顶的数据比较判断直到文件中的所有数据都被遍历判断后终止打印结果并释放堆空间。3.其他应用场景简介1.图算法中的最短路径与最小生成树简介Dijkstra 算法和 Prim 算法均利用优先队列来快速抽取当前距离最小或权值最小的顶点从而将复杂度从 O(V²) 优化至 O((VE)*logV)。2.中位数维护与数据流统计简介使用两个堆(大根堆存较小一半小根堆存较大一半)可以 O(logN) 地动态维护数据流的中位数类似思想还可用于求百分位数等。3.定时器与事件驱动简介很多定时器实现使用小根堆以最近超时时间作为键便于快速获取下一个到期事件。四、总结1.一份测试代码包含堆的各项操作堆排序和TopK问题的完整测试代码。voidTest_Heap(){inta[10]{4,2,8,1,5,6,9,7};HP hp;#初始化测试HPInit(hp);#遍历插入数组中的值排成小堆for(inti0;isizeof(a)/sizeof(a[0]);i){#添加数据测试HPPush(hp,a[i]);}#判断是否为空测试while(!HPEmpty(hp)){#获取堆顶元素测试printf(%d ,HPTop(hp));#删除数据测试HPPop(hp);}printf(\n);#销毁堆测试HPDestroy(hp);#堆排序测试HeapSort(a,sizeof(a)/sizeof(a[0]));#TopK问题测试Test_TopK();}2.整体总结➤堆作为一种基于完全二叉树的优先级容器以其简洁的数组存储和高效的对数级操作成为计算机科学中最实用的数据结构之一。它的核心在于“有序的父子关系”而非“全局有序”这种局部有序性恰好满足了大多数场景下“只关心极值”的需求。➤最后堆并非万能查找操作需要 O(N)因不支持随机访问也不适合频繁修改非堆顶元素。了解其优势与局限才能在实际开发中做出正确的选择。⚛️EL PSY CONGROO十分感谢你的阅读本期不确定是否应该补充向上调整建堆算法的时间复杂度数学分析