网站导航
> 文档中心 > 堆的经典——TopK问题与堆排序

堆的经典——TopK问题与堆排序

网友: 文档中心 2022-03-28 12:06:49

文章目录

  • 🍁Topk问题的引入
  • 🌴Topk问题
  • 🌴堆排序
  • 🌴排升序到底选大堆还是小堆
    • 🌏排升序建小堆分析
    • 🌏排升序建大堆
  • 🍁时间复杂度证明
    • 🌏调整算法的时间复杂度
    • 🌏建堆的时间复杂度

前面这篇文章已经具体讲解过堆的性质与实现了
数据结构——堆
堆的经典——TopK问题与堆排序

这篇文章将介绍堆中经典的Topk问题与堆排序

🍁Topk问题的引入

要求：从N个数中找出前K个最大的数(N >> K)
方法一：假设是从100个数中找前10个最大的数，先用快排排降序，前十个就是最大的，时间复杂度O(NlogN)
方法二：将N个数依次push到大堆中，那么堆顶的元素肯定是最大的，然后popK次，就找到了前K个最大的数，时间复杂度O(N+k*log2N后面会再次证明)。那这应该就是Topk问题了吧，显然不是

堆的经典——TopK问题与堆排序
当N非常大，为10亿、20亿大到内存中无法存下这些数，只能存储在磁盘中，那上面的两种方式就不适用了

🌴Topk问题

虽然无法将N个数都建成大堆，但可以

  • 先将前K个数建为小堆，小堆的特点就是堆顶的数是最小的，大数往堆底沉
  • 当用后N-K个数不断和堆顶比较后然后向下调整后，
  • 最后堆中的K个数就是前K个最大的
  • 时间复杂度为：K+（N-K）* logK 也就是O（NlogK）

这里建立的是小堆而不是大堆，因为如果是大堆，那么堆顶的数是堆中最大的，和剩下的N-K个数比较时，如果当前堆顶的数就是N个数中最大的，那么就把后面的数都挡在堆外了，这种只能找到N个数中最大的数

前面已经实现过堆了

typedef int HPDataType;typedef struct Heap{HPDataType* p;int size;int capacity;}HP;//堆初始化void HeapInit(HP* pc);//堆中元素交换void HeapSwap(HPDataType* p1, HPDataType* p2);//打印元素void HeapPrint(HP* pc);//堆插入void HeapPush(HP* pc, HPDataType x);//堆删除void HeapPop(HP* pc);//堆销毁void HeapDestroy(HP* pc);//堆判空bool HeapEmpty(HP* pc);//向上调整void AdjustUp(HPDataType* p, int child);//向下调整AdjustDown(HPDataType* p, int n, int parent);//获取堆顶元素HPDataType HeapTop(HP* pc);

我们模拟实现从1w个数中找到最大的前10个数

void PrintTopK(int* p, int N, int K){//前K个数建为小堆HP h1;//初始化HeapInit(&h1);for (int i = 0; i < K; i++){HeapPush(&h1, p[i]);}//剩余的N-K个数分别与堆顶的元素比较，大于堆顶元素则交换然后向下调整，大的数都沉入堆底for (int i = K; i < N; i++){if (p[i] > HeapTop(&h1)){HeapPop(&h1);HeapPush(&h1, p[i]);}}HeapPrint(&h1);HeapDestroy(&h1);}void TopK1(){srand((unsigned int)time(NULL));int N = 10000, K = 10;int* p = (int*)malloc(sizeof(int) * N);//将N个数都初始化为小于100万的数for (int i = 0; i < N; i++){p[i] = rand() % 1000000;}//随机取K个大于100万的数放入数组p[1010] = 1000001;p[2555] = 2000000;p[377] = 3000000;p[4781] = 3003456;p[5433] = 4006754;p[675] = 9874567;p[7954] = 8532876;p[4578] = 3489645;p[6775] = 4892111;p[789] = 9999999;PrintTopK(p, N, K);}int main(){TopK1();return 0;}

在这里插入图片描述再演示一下从文件中读取C语言文件读取
测试就只选从6个数总找出最大的前3个，这里在text文件中写入了6个数
在这里插入图片描述测试无误的话就会打印后面的三个数

void TopK2(){int N = 6, K = 3;int* p = (int*)malloc(sizeof(int) * N);FILE* pf = fopen("D:\\桌面\\text.txt", "r");int i = 0;int arr[1] = { 0 };while (fscanf(pf, "%d", arr) != EOF){p[i] = arr[0];++i;}fclose(pf);pf = NULL;PrintTopK(p, N, K);}int main(){TopK2();return 0;}

在这里插入图片描述以上就是Topk问题，关于这些时间复杂度后面会证明，下面先讲堆排序

🌴堆排序

如果要对以下数组升序，可以先将数组中的元素建成一个小堆，然后重新pop到数组中，而这样空间复杂度就是O(N)

int arr[] = { 70, 56, 30, 60, 25, 40 };

堆排序是通过建堆的思想直接在数组中进行排序，空间复杂度为O(1)

比如我们要建一个小堆，就是不断插入数据，然后向上调整，那么我那就可以利用向上调整的思想，直接在数组中进行排序

方法一：向上调整法，从左往右遍历数组
在这里插入图片描述

#include #include void HeapSwap(int* p1, int* p2){assert(p1 && p2);int tmp = *p1;*p1 = *p2;*p2 = tmp;}void AdjustUp(int* p, int child){assert(p);int parent = (child - 1) / 2;while (child > 0){//小于父亲节点就调整if (p[child] < p[parent]){HeapSwap(&p[child], &p[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}void sortHeap(int* p, int n){assert(p);for (int i = 1; i < n; i++){AdjustUp(p, i);}}int main(){int arr[] = { 70, 56, 30, 60, 25, 40 };int n = sizeof(arr) / sizeof(arr[0]);sortHeap(arr, n);return 0;}

方法二：向下调整法，从右往左遍历数组

在这里插入图片描述

#include #include void HeapSwap(int* p1, int* p2){assert(p1 && p2);int tmp = *p1;*p1 = *p2;*p2 = tmp;}AdjustDown(int* p, int n, int parent){//左孩子int child = parent * 2 + 1;while (child < n){//判断是否有右孩子且右孩子小于左孩子if (child + 1 < n && p[child + 1] < p[child])++child;if (p[child] < p[parent]){HeapSwap(&p[child], &p[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}void sortHeap(int* p, int n){assert(p);int child = n - 1;int end = (child - 1) / 2;while (end >= 0){AdjustDown(p, n, end);--end;}}int main(){int arr[] = { 70, 56, 30, 60, 25, 40 };int n = sizeof(arr) / sizeof(arr[0]);sortHeap(arr, n);return 0;}

🌴排升序到底选大堆还是小堆

🌏排升序建小堆分析

上面我们用向下调整法建成小堆后，堆顶的元素就是最小的，放在数组的第一个位置，那如何选择次小的呢？

把25不看作堆中的元素，将arr[1]~arr[5]的数据重新建小堆再找次小的数，以此类推，但这样堆的结构就乱了，每次都需要更新堆的根节点，而且建堆的时间复杂度是O(N)，那么排成升序的时间复杂度就是N*(N-1)*(N-2)…11也就是O(N2)，那么堆排序就没有意义了
在这里插入图片描述

🌏排升序建大堆

参考堆的pop接口，是将堆顶与堆尾的数据交换后再--size也就pop掉堆顶的元素了，所以只需要保证交换后堆尾的数最大，也就是交换之前堆顶的数最大，这就是大堆的结构了，所以排升序要建大堆
在这里插入图片描述将最大的数跟最后一个数交换，然后不把最后一个数看作堆中的元素，堆顶的数向下调整后就可以选出次小的数，以此类推最后就能排出升序，向下调整的时间复杂度为O(log2N)
在这里插入图片描述

int arr[] = { 70, 56, 30, 60, 25, 40 };

在这里插入图片描述

#include #include void HeapSwap(int* p1, int* p2){assert(p1 && p2);int tmp = *p1;*p1 = *p2;*p2 = tmp;}AdjustDown(int* p, int n, int parent){//左孩子int child = parent * 2 + 1;while (child < n){//判断是否有右孩子且右孩子小于左孩子if (child + 1 < n && p[child + 1] < p[child])++child;if (p[child] < p[parent]){HeapSwap(&p[child], &p[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}//这里实现堆排序一个向下调整就解决了，所以没有用向上调整void sortHeap(int* p, int n){assert(p);int child = n - 1;//从最后一个非叶子节点开始，向下调整int first = (child - 1) / 2;while (first >= 0){AdjustDown(p, n, first);--first;}int right = n - 1;while (right > 0){HeapSwap(p, p + right);AdjustDown(p, right, 0);--right;}}int main(){int arr[] = { 70, 56, 30, 60, 25, 40 };int n = sizeof(arr) / sizeof(arr[0]);sortHeap(arr, n);for (int i = 0; i < n; i++){printf("%d ", arr[i]);}return 0;}

所以堆排序本质上是一种选择排序

  • 排升序，建大堆
  • 排降序，建小堆

大小堆直接的转化也是非常容易的，只需要调整向上和向下调整的比较关系
在这里插入图片描述

🍁时间复杂度证明

🌏调整算法的时间复杂度

为了方便， 以堆为满二叉树证明
满二叉树的节点个数n=2h-1–>h=log2n+1
向上调整或向下调整的时间复杂度与树的高的有关，所以插入一个数据的时间复杂度为O(log2N)，但插入N个数据（建堆）的时间复杂度并不是O(N*log2N)
在这里插入图片描述

🌏建堆的时间复杂度

建堆的时间复杂度与向上调整或向下调整有关，考虑最坏情况：
在这里插入图片描述

总结：TopK问题可以通过建小堆，找到N个数中最大的前K个，通过建大堆，找到N个数中最小的前K个
堆排序：排升序建大堆，排降序建小堆

以上就是堆中经典的Topk问题与堆排序了，希望我的文章对你有所帮助，欢迎👍点赞 ，📝评论，🌟关注，⭐️收藏
在这里插入图片描述

新能源吧

网络标签：

相关问题