小工具知识网

当前位置: 首页 > 行业知识 > 数据结构——堆的应用 Topk问题

行业知识

数据结构——堆的应用 Topk问题

2026-11-16 10:06:57 来源:互联网转载

前言

hello hello~ ,这���是大耳朵土土垚~ ,欢迎大家点赞关注收藏

个人主页:大耳朵土土垚的博客

所属专栏:数据结构学习笔记 、C语言系列函数实现

对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可以写在评论区或者私信我哦~

前面我们学习了利用堆进行排序,今天我们将继续介绍利用堆解决前k个最值的问题,Topk问题(在N个数中找出最大的前k个)在实际生活中也非常常见,比如店外卖时评分最高的前十家店铺,玩王者时英雄战力前十名等与排序排名有关的应用。

解题思路

正常思路 将这N个数建成一个大堆,然后Popk次,就可以找出最大的前k个 ;

但是如果N非常大以亿计(10亿个整数所占空间大概4G)那么就会非常耗时耗力,难以计算。

这里给出一种更好的解决办法:

①将前k个数建成小堆;(必须是小堆哦~)

②后面N-k个数依次比较,如果比堆顶的数据大,就替换它进堆;

③然后将替换后的再向下调整使之重新成为一个小堆;

④最后这个小堆的值就是最大的前k个。

在写题之前我们先要创造N个数,可以通过c语言的文件操作以及随机生成函数来获得并写入文件中:

代码如下:

#include//创造N个数据void CreatData(){//造数据int n = 1000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int  i = 0; i    

✨✨这里使用了srand生成随机数需要包含time.h头文件;

int x = rand() % 10000;这个式子可以帮助我们生成10000以内的随机数;

fprintf可以帮助我们将生成的随机数写入到文件中(如下图生成了data文件):

所以生成文件后为了找到最大的前k个,我们可以手动改一些数据来验证后续代码的正确性:

这里手动改了5个,后面如果找出这五个最大的数就说明我们写的代码是正确的啦~

为了保证文件数据不被覆盖,我们在运行一次CreatData()函数之后就可以把它屏蔽掉了,此时已经生成了n个数据的文件data.txt了。

int main(){//CreatData();//屏蔽PrintTopk(5, 1000);return 0;}

Topk排序

造完数据后我们就可以利用之前学习过的堆来求出Topk啦

代码如下:

void PrintTopk(int k,int n){//打开文件const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}//创建顺序表开辟空间int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");return;}//从文件中读取k个数for (int i = 0; i = 0; i--){AdjustDown(kminheap, k, i);}//将剩余N-k个数依次与堆顶元素比较for (int i = 0; i  kminheap[0]){Swap(&tmp, &kminheap[0]);AdjustDown(kminheap, k, 0);}}//打印前k个元素for (int i = 0; i    

对于造小堆以及排序有疑问的可以看看土土的上篇博客——堆排序详解

运行代码如下:

int main(){//CreatData();PrintTopk(5, 1000);return 0;}

运行结果如下:

完全正确~是我们之前改的那五个数,说明我们的代码将它从1000个数中找了出来至此Topk问题得到解决 ~

✨✨这里再提一句,打印出来的虽然是n个数中的最大的k个但是我们发现打印的顺序是乱的,通过之前排序的学习,大家知道怎么将他们按顺序打印出来吗?有兴趣的小伙伴可以尝试一下~

结语

上一篇:tt语音怎么解除绑定服务器?

下一篇:夏天主机发烫黑屏怎么办