珠海网站网站建设新网站做百度推广

前言：

本文TopK问题是在数据量很大的前提下进行解决，当数据量足够大时，内存中存不下，只能存到文件硬盘中。当存到硬盘中，我们无法用建堆，一个一个pop取出最值的方式解决，因为我们没法在硬盘中去访问数组下标。那怎么解决呢？

问题背景：

假设有10亿个数据，内存存不下，数据在文件中，找出最大的前K个 K == 100

解题思路：

1. 读取文件中前K个数据，在内存数组中建立一个小堆
2. 再依次读取剩下数据，跟堆顶数据比较，大于堆顶，就替换他进堆，接着进行向下调整算法
3. 所有数据读完，堆里面的数据就是最大的前100个

解析：

为什么不能用大堆？

假设最大的数据在前面已经进堆，那么堆顶元素就是最大的，此时堆顶元素就挡住了剩余其他前TopK的元素进堆。

建立小堆的妙处：

只要大于堆顶，就会进堆，较大的数据就会往后面靠，小的数据在前面，不会影响剩下较大的数据进堆。

时间复杂度：O(N*logK)

空间复杂度：O(K)