网站建设的目的与意义是什么,轻松筹 做的网站价格,网站建设策划师,中国世界排名变化前言#xff1a;
本文TopK问题是在数据量很大的前提下进行解决#xff0c;当数据量足够大时#xff0c;内存中存不下#xff0c;只能存到文件硬盘中。当存到硬盘中#xff0c;我们无法用建堆#xff0c;一个一个pop取出最值的方式解决#xff0c;因为我们没法在硬盘中去…前言
本文TopK问题是在数据量很大的前提下进行解决当数据量足够大时内存中存不下只能存到文件硬盘中。当存到硬盘中我们无法用建堆一个一个pop取出最值的方式解决因为我们没法在硬盘中去访问数组下标。那怎么解决呢
问题背景
假设有10亿个数据内存存不下数据在文件中找出最大的前K个 K 100
解题思路
读取文件中前K个数据在内存数组中建立一个小堆再依次读取剩下数据跟堆顶数据比较大于堆顶就替换他进堆接着进行向下调整算法所有数据读完堆里面的数据就是最大的前100个
解析
为什么不能用大堆
假设最大的数据在前面已经进堆那么堆顶元素就是最大的此时堆顶元素就挡住了剩余其他前TopK的元素进堆。
建立小堆的妙处
只要大于堆顶就会进堆较大的数据就会往后面靠小的数据在前面不会影响剩下较大的数据进堆。
时间复杂度O(N*logK)
空间复杂度O(K)
