欢迎光临
我们一直在努力

数据结构:堆的应用:Top-K问题

如果我们要存储1亿个整数,需要多大内存?
在这里插入图片描述
可以看到达到了九位数,我们知道内存空间的换算是这样的:
1GB=1024MB=1024 * 1024KB=1024 * 1024 * 1024Byte
1GB差不多就是1亿字节的大小了,我们知道一个整数占4个字节,所以存储这1亿个整数需要4GB的内存。

现在只有1KB的内存,那么如何存储这些数据呢?
我们求这1亿个数据中前k个最大/最小的数据,假如说有n个数据,我们从中取前k个数据(k<<n)建成一个堆,然后遍历后n-k个数据。
我们知道堆顶数据是最值,如果我们建大堆,遍历的后n-k个数据如果小于堆顶数据则交换,到最后得到的堆就是k个最小的数据。如果是小堆则反之。

我们先造数据出来,我们写100000个小于1000000的整数到名为“data.txt”的文件中。
在这里插入图片描述
在这里插入图片描述
文件建出来了,我们要取k个最大的数据,为了方便之后验证函数是否正确,我们手动改数据改成10个最大的数据:
在这里插入图片描述
然后开始从文件中取k个元素:
在这里插入图片描述
在这里插入图片描述
然后将这个数组建成一个小堆,我们之前学堆排序的时候学过,这里用向下排序算法,就直接用了:
在这里插入图片描述
然后我们再遍历后n-k个元素,如果比堆顶大,则交换堆顶,再保持为小堆结构,遍历完即可得到k个最大的元素。
在这里插入图片描述
使用完记得关闭文件,然后打印数组,打印完把malloc申请的空间释放掉。
在这里插入图片描述
打印结果是这样的:
在这里插入图片描述
是排成小堆结构的k个最大数据,代码逻辑没问题,Top-K问题成功解决。

赞(0)
未经允许不得转载:171主机测评 » 数据结构:堆的应用:Top-K问题
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址