您的位置:首页 > 教育 > 锐评 > 文件中找TopK问题 的详细讲解

文件中找TopK问题 的详细讲解

2024/10/6 5:57:33 来源:https://blog.csdn.net/shylyly_/article/details/141173398  浏览:    关键词:文件中找TopK问题 的详细讲解

一:问题:

  • 从一个包含10000整数的文件中找出最大的前10个数。

二:方法:

1:先直接拿文件的前10个数,建造一个小堆

2:再依次读取文件中,剩下的数,比堆顶大,则替换堆顶,然后进行向下调整

最后,堆里的十个数据就是最大的十个整数

三:解释

Q1:为什么找最大的前10个数字,不是建大堆?

A1:如果最大的那一个数字位于堆顶,那么方法中的第2步,再也没有比堆顶大的数字,别说其余的最大的前9个数,应该是在最大数字后面的所有数字压根进不去堆

Q2:为什么是向下调整,不是向上调整?

A2:时间复杂度,向下远远优于向上,详情博客:向上or向下调整建堆 的时间复杂度的本质区别的讲解-CSDN博客

Q3:不会出现一个较大数字卡在堆顶的情况吗?比如最大的数字在堆顶,其他数字就进不去堆?

A3:较大数字永远不会卡在堆顶,因为这是一个小堆,根据向下调整,较大的都会在下面。

Q4:为什么最后剩的就是最大的10个数字?

A4:比堆顶大就能进堆,再加上小堆性质,最后的就是最大的10个数字

下面看一个例子:

从1 3 5 7 9 2 4 6 8 10 中,找出最大的前3个数字

1:先直接拿文件的前3个数,建造一个小堆

2: 再依次读取文件中,剩下的数,比堆顶大,则替换堆顶,然后进行向下调整

最后的小堆里面就是最大的3个数!

四:代码展示:

A:造数据函数

解释:

1:该部分一般是作为题目的已知条件

2:此函数生成了1万个随机数,这些数字被放在了一个data.txt 的文件里面。

B:topkprint函数

解释:

1:文件的读写函数,不了解可以看博主的此篇博客:

八种顺序读写函数的介绍(fput/getc;fput/gets;fscanf,fprintf;fwrite,fread)-CSDN博客

2:(重点)

对已知大小的数组进行向下调整建立堆,不用从最后一排节点开始,因为最后一排的节点都无法进行向下调整。

Q1:那从哪一个节点开始?倒数第二排的最右面一个吗?

A1:不一点是第二排的最右面个节点,因为此节点也有可能无孩子节点,这样的话,也无法进行向下调整。所以是从倒数第一个非叶子节点开始调整(也就是最后一个节点的父亲),根据找父亲的公式parent = (child-1)/2,所以为(k-1-1)/ 2,也就是图里的(k-2)/2,第一个-1就得到最后一个整数的下标,第二个-1就是公式里的了。

C:main函数

D:结果

E:检测

怎么知道这10个数字是最大的十个数字呢?

检测方法如下:

1:

2:打开文件夹中我们创建的data.txt

3:手动修改10个数字,分别为1亿 2亿..........10亿

可得结果:

 可知,代码是对的。

注意:修改的时候,不要超过整形的范围。

版权声明:

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

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