💛 前情提要💛
本章节是数据结构的堆的应用的相关知识~
接下来我们即将进入一个全新的空间，对代码有一个全新的视角~
以下的内容一定会让你对数据结构有一个颠覆性的认识哦！！！
?以下内容以C语言的方式实现，对于数据结构来说最重要的是思想哦?
以下内容干货满满，跟上步伐吧~
作者介绍：
🎓 作者： 热爱编程不起眼的小人物🐐 🔎作者的Gitee：代码仓库 📌系列文章&专栏推荐： 《刷题特辑》、 《C语言学习专栏》、《数据结构_初阶》
📒我和大家一样都是初次踏入这个美妙的“元”宇宙🌏 希望在输出知识的同时，也能与大家共同进步、无限进步🌟
📌导航小助手📌 💡本章重点🍞堆的应用🥐Ⅰ.堆排序🥐Ⅱ.Top-K问题🏷?最小的K个数【难度：简单】?? 思路一：堆排序?? 思路二： 建堆?? 思路三： 建前K个数的堆 🥯Ⅲ.总结 🫓总结
💡本章重点
堆排序
Top-K问题
🍞堆的应用 🥐Ⅰ.堆排序
💡堆排序：
本质为选择排序的一种
堆排序便是利用堆这种数据结构的思想进行排序
?如果有同学不太熟悉堆，可点击?跳转?补充知识再出发呀
🔥 思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完?思考： 如何利用堆进行排序
假如排升序，我们利用小堆进行排序的话：
我们建好一个小堆后，因为小堆的特性为最小的数在根节点处（最上面），我们便排好升序中的第一个数字
此时我们再继续排剩下的数字，便需要在建堆的时候剔除已经排好的数字，继而将剩下的重新的建堆，选最小的数字
重复上述步骤即可
?特别注意：
如果按照上述方法进行排序的话，有两个问题：
🔴第一次建好堆后，在选出最小的数字放到第一个位置紧接着要选出次小的（即进行第二次建堆选数，谁去做新的根节点），如何选？
Eg：
🟠假如按数组的下标顺下去，让下一个数作为新的根结点（即指上图中的5）的话，那树原来的结构就被打乱了，需要重新建堆，才能再次选出最小的
建堆的时间复杂度为 O ( N ) O(N) O(N)，那整体排序下来时间复杂度便为 O ( N 2 ) O(N^2) O(N2)🟡最终发现如果按照这种方式进行排序的话，相当于建堆的作用就是选数，还不如直接遍历数组选数进行排序，那次是堆排序就没有意义了
?但事实真的是这样吗？并不！
??方法：
1??建堆假如我们调转一下思路，排升序不用小堆，而是：
升序：建大堆
降序：建小堆
Eg：
2??利用堆删除的思想进行排序 将堆顶的数据与堆尾数据进行交换，这样就达到排好最大值的效果将排好的数字不再纳入建堆中【即建堆的目的就是选出最大值，所以已经选出来的，就无需要再参加】
并将交换后产生新的树进行重新建堆【因为此时只有根节点发生变化，而左、右子树的关系并没有改变，所以可以利用向下调整算法进行建堆】
重复上述步骤即可，直至堆里只剩下一个元素，才截止?动图示例： 完整过程
?综上：堆排序的代码实现【时间复杂度： O ( N ? l o g N ) O(N*logN) O(N?logN)】
void ADjustDown(int * a, int n, int parent) { //大堆 int child = parent * 2 + 1; while (child < n) //当 孩子的下标 超出 数组的范围，则说明不存在 { //1.选出左右孩子中，较小的一个 //child -- 左孩子下标；child+1 -- 右孩子下标 if (child + 1 < n && a[child + 1] > a[child]) { //想象的时候：默认左孩子是比右孩子小 //如果大的话，child就走到右孩子下标处 child++; } //2.交换 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { //满足的情况 break; } } } void HeadSort(int* a,int n) { //建堆 --- 时间复杂度:O(N) //大堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { ADjustDown(a, n, i); } int end = n - 1; while (end > 0) //end = 0的时候就截止：即 长度为0就截止 { Swap(&a[0], &a[end]); //选出次大值 ADjustDown(a, end, 0); end--; } } 🥐Ⅱ.Top-K问题💡Top - K：
意思就是：求数据中前K个最大的元素或者最小的元素
比如：在高考出成绩时，需要对全省考生的成绩进行排序并取出前50名考生的成绩进行封锁，此时就涉及Top-K问题了
👉我们便以题目去理解它吧~
🏷?最小的K个数【难度：简单】🔍题目传送门：
输入整数数组 arr ，找出其中最小的 k个数
例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4
示例 1： 输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1] 示例 2： 输入：arr = [0,1,2,1], k = 1 输出：[0]💡解题关键： 找出前K个最小的元素
?? 思路一：堆排序 利用我们刚刚所学的堆排序，对数组进行排序，然后取出前K个即可?特别注意：
我们需要自己先实现一个堆排序，再进行使用在用完堆后，记得销毁，否则会造成内存泄露👉实现：
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize) { int* returnArray = (int*)malloc(k * sizeof(int)) ; HeadSort(arr,arrSize); for(int i = 0; i < k; i++) { returnArray[i] = arr[i]; } *returnSize = k; return returnArray; }💫但目前堆排序的效率为： O ( N ? l o g N ) O(N*logN) O(N?logN)，是否还能优化呢？
?答案是可以的
?? 思路二： 建堆根据题意，我们只需要取出最小的前K个数即可，那我们便可以不对数组进行排序，而是利用小堆的特性：每个父亲结点的值总是≤孩子结点的值
只需要对这个数组进行建堆（建成小堆）即可，然后每次都取出根节点（最小值），一共取K次，便是最小的前K个元素
?特别注意：
我们需要自己先实现一个堆，再进行使用👉实现：
1??实现堆
typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; void Swap(HPDataType* p1, HPDataType* p2); void AdjustDwon(HPDataType* a, int size, int parent); void AdjustUp(HPDataType* a, int child); void HeapDestroy(HP* php); void HeapPop(HP* php); HPDataType HeapTop(HP* php); void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } void HeapInit(HP* php, HPDataType* a, int n) { assert(php); php->a = (HPDataType*)malloc(sizeof(HPDataType)*n); if (php->a == NULL) { printf("malloc fail\n"); exit(-1); } //1.拷贝 memcpy(php->a, a, sizeof(HPDataType)*n); php->size = n; php->capacity = n; //2.建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDwon(php->a, php->size, i); } } void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = php->capacity = 0; } void AdjustUp(HPDataType* a, int child) { int parent = (child - 1) / 2; //while (parent >= 0) while (child > 0) { //if (a[child] < a[parent]) if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } //建小堆 void AdjustDwon(HPDataType* a, int size, int parent) { int child = parent * 2 + 1; while (child < size) { // 选出左右孩子中小/大的那个 if (child+1 < size && a[child+1] < a[child]) { ++child; } // 孩子跟父亲比较 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapPop(HP* php) { assert(php); assert(php->size > 0); Swap(&(php->a[0]), &(php->a[php->size - 1])); php->size--; AdjustDwon(php->a, php->size, 0); } HPDataType HeapTop(HP* php) { assert(php); assert(php->size > 0); return php->a[0]; }2??实现Top-K
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize) { HP hp; HeapInit(&hp,arr,arrSize); int* retArr = (int*)malloc(sizeof(int)*k); for(int i = 0;i < k; i++) { retArr[i] = HeapTop(&hp); HeapPop(&hp); } HeapDestroy(&hp); *returnSize = k; return retArr; }💫但目前堆的效率为： O ( N + k ? l o g N ) O(N + k*logN) O(N+k?logN)，是否还能优化呢？
?答案是可以的
?? 思路三： 建前K个数的堆类似于建堆的操作，但不同的是，建堆是对数组内全部元素进行调整
但我们现在只需要针对前K个数进行建堆即可
?特别注意：
找前k个最大的元素，则建小堆
找前k个最小的元素，则建大堆
👉步骤：
1??用数据集合中前K个元素来建堆【因为这里需要找前K个最小的元素，所以建大堆】
2??剩余的N-K个元素（N为总元素个数）依次与堆顶元素来比较，不满足则替换堆顶元素，再向下调整
3??将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素
【我们现在这里建的是大堆，如果与堆顶元素比较时，外面的某个元素小于堆顶的值，则为不满足】
?特别注意：
🔴本质：通过数组剩下的N-K个元素，找到比前K个元素的堆中的堆顶元素小的元素，进行轮换
1??即在剩下的元素中，找到比堆顶还小的元素，不断轮换堆中元素的最大值
2??因为要找的是最小的K个元素，所以最小的前K个一定比大堆堆顶的数据小，一定可以进堆中
🟡这也是为什么建大堆的原因，保证前K个最小的元素中的最小值进来一定不会在堆顶位置（以防前K个最小的元素中的最大值进不来）
🔵现在即使是前K个最小的元素中的最大值进堆，那前K-1个最小的元素还是依然可以进堆
🟣直至这K个数据的堆不再进入元素，说明此时堆内的K个数据就是前K个最小的元素【堆外面没有比这K个元素更小的数了】
?亮点：
1??在面对大量数据且无论多大的时候，需要解决Top-K问题时，这个方法依然受用，因为我们始终是在维护一个K个数的堆【只需要遍历剩下的元素进行比较、进堆、向下调整而已】
2??此方法的时间复杂度始终为： O ( ( N ? K ) ? l o g K ) O((N-K )*logK) O((N?K)?logK)
这是因为需要遍历N-K 个元素与堆顶元素进行比较
若不满足进堆后，需要向下调整（有K个元素进行向下调整）【 O ( l o g k ) O(logk) O(logk)】
3??此方法的空间复杂度为： O ( K ) O(K) O(K)
?动图示例：
👉实现：
1??实现建堆
void Swap(HPDataType* p1, HPDataType* p2); void AdjustDwon(HPDataType* a, int size, int parent); void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } //建大堆 void AdjustDwon(HPDataType* a, int size, int parent) { int child = parent * 2 + 1; while (child < size) { // 选出左右孩子中小/大的那个 if (child+1 < size && a[child+1] > a[child]) { ++child; } // 孩子跟父亲比较 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }2??实现Top-K
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize) { if(k == 0) { *returnSize = 0; return NULL; } int* arrRet = (int*)malloc(sizeof(int)*k); //找前K个最小 -- 前k个数建大堆 for(int i = 0; i < k; i++) { arrRet[i] = arr[i]; } for(int j = (k-1-1) / 2; j >= 0; j--) { AdjustDwon(arrRet,k,j); } //剩下的N-K个数，比堆顶小的，就替换堆顶数据，进堆调整 for(int l=k;l<arrSize; l++) { if(arr[l] < arrRet[0]) { arrRet[0] = arr[l]; AdjustDwon(arrRet, k, 0); } } *returnSize = k; return arrRet; } 🥯Ⅲ.总结?综上：就是堆的应用啦~
??相信大家对堆的应用有不一样的看法了吧🧡
🫓总结
综上，我们基本了解了数据结构中的 “堆的应用” 🍭 的知识啦~~
恭喜你的内功又双叒叕得到了提高！！！
感谢你们的阅读😆
后续还会继续更新💓，欢迎持续关注📌哟~
💫如果有错误?，欢迎指正呀💫
?如果觉得收获满满，可以点点赞👍支持一下哟~?
 1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。 |
