堆排序可以很好解决TopK问题
时间复杂度 N(logN),不稳定排序,相同大小数据仍可能交换位置
寻找海量数据中最大的100个数据,可以建立容量100的小顶堆,然后将后面的数据与堆顶最小值比较,
如果比它大,进行交换重新将堆进行调整,后面数据以此类推,可以得到top 100的数据
TopK问题,一亿数据找最大10000
建立10000的最小堆,数据依次放入堆,比堆顶大则互换下沉,建堆O(nlogn) 总时间复杂 O(mnlogn) m=一亿 n=10000
下面简单例子
还可以分别放在1000个文件分别找到前10000然后合并排序。