当前位置: 首页> 财经> 金融 > 堆排序经典问题【TopK】

堆排序经典问题【TopK】

时间:2025/7/16 4:15:50来源:https://blog.csdn.net/2301_80216111/article/details/139582213 浏览次数:0次

前言

在上文我们讲了堆排序的实现(点此调整),我们先简单回顾一下。
在进行堆排序之前,需要建一个堆,由于排序是将堆顶数据与堆底交换,所以排升序建大堆,降序建小堆。
堆排序的代码

//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child+1 < n && a[child] < a[child + 1]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}//向下调整创建堆
void CreateHeap(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}
}//堆排序
void HeapSort(int* a, int n)
{CreateHeap(a, n);int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}}
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}int main()
{int a[] = { 5,6,8,2,3,7,10,4,9,1 };printf("排序前:");PrintArray(a, sizeof(a) / sizeof(int));//CreateHeap(a, sizeof(a) / sizeof(int));HeapSort(a,sizeof(a) / sizeof(int));printf("排序后:");PrintArray(a, sizeof(a) / sizeof(int));return 0;
}

TopK问题

假设给你10亿个整数(大小约为3.73G),让你找出最大\最小的前k个数。

情况一(无内存限制)

在不管内存的情况下我们可以直接建造一个能存放4亿的整数的堆,再继续堆排序,取出前k个数据。

情况二(内存只有1GB)

那么这时候给你一个限制,如果这个内存只有1G该怎么办。(四亿个整型的数据存放再硬盘)
这很简单,我们可以分四次从硬盘中读取,然后每次取出最大/最小的前k个数,最后再从这4个前k个数中求最大/最小的前k个数。

情况三(内存只有1KB)

我们同样可以使用情况二的方法,只剩读取的次数变多的,但是但是,这样的效率就太慢了。
这时候就有一个很优的方法:我先建K个数的小堆,让我从硬盘中读取的数据与堆顶数据比较,如果大于,就将堆顶数据替换成读取的数据,然后再向下调整。
由于我建的是小堆,就绝对能确定堆顶数据是堆中最小的数据,如果我的堆顶数据就是第K大的数据,就代表我这个堆里的数据就前K大的数据。
当我要找前k小的时候,将建造K个数的大堆就可以了,其他操作都大致相同,只需要修改大小于号就可以了。

//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child+1 < n && a[child] < a[child + 1]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}//打印数组
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void CreateNDate()
{// 造数据int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void PrintTopK(int k)
{const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int* KMinHeap = (int*)malloc(k * sizeof(int));if (KMinHeap == NULL){perror("malloc fail");exit(1);}for (int i = 0; i < k; i++){fscanf(fout, "%d", &KMinHeap[i]);}for (int i = (k - 2) / 2; i > 0; i--){AdjustDown(KMinHeap, k, i);}int val = 0;while (fscanf(fout, "%d", &val) != EOF){if (val > KMinHeap[0]){KMinHeap[0] = val;AdjustDown(KMinHeap, k, 0);}}printf("前%d大的数:", k);PrintArray(KMinHeap, k);fclose(fout);
}int main()
{//CreateNDate();PrintTopK(10);return 0;
}

在这里插入图片描述
注:
这前十个数都是自己造的数,这些数是一定大于其他数的,我们可以用这些自己造的数来确认是否成功。
这里的TopK并没有要求需要排序,只是要求找出前K个最大(最小)数,如果你要排序,就调用堆排序的函数就可以了。

结语

最后感谢您能阅读完此片文章,如果有任何建议或纠正欢迎在评论区留言,也可以前往我的主页看更多好文哦(点击此处跳转到主页)。
如果您认为这篇文章对您有所收获,点一个小小的赞就是我创作的巨大动力,谢谢!!!

关键字:堆排序经典问题【TopK】

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: