堆排序可以很好解决TopK问题

时间复杂度 N(logN),不稳定排序,相同大小数据仍可能交换位置

寻找海量数据中最大的100个数据,可以建立容量100的小顶堆,然后将后面的数据与堆顶最小值比较,

如果比它大,进行交换重新将堆进行调整,后面数据以此类推,可以得到top 100的数据

 

  

 

TopK问题,一亿数据找最大10000

建立10000的最小堆,数据依次放入堆,比堆顶大则互换下沉,建堆O(nlogn)  总时间复杂 O(mnlogn)  m=一亿  n=10000

下面简单例子

 

还可以分别放在1000个文件分别找到前10000然后合并排序。