本文共 719 字，大约阅读时间需要 2 分钟。

题目：从N=100 0000个数中找出最大的前m=100个数

最小堆

1 建立m=100的最小堆,heapify方法从数组变为最小堆的复杂度为O(m)

2 剩下的N-m个依次与堆顶元素比较，若大于，就替换堆顶元素，然后调整堆结构（下沉),(N-m)logm，最后堆内的元素就是所求 总时间复杂度为 O(m)+O((N-m)logm)=O(Nlogm)

分块+最小堆

如果不能从磁盘读取那么多，可以分块，将100万分成100个1万，对每个1万进行上述操作。即O(Nlogm),N=10000,m=100.

此时，每块都找到了100个最大的，然后再对100块*100个数据做上述最小堆操作。时间复杂度同上。 最终的时间复杂度为也是O(Nlogm)。N=100 0000,m=100

类似的，前k小用最大堆

参考：

https://blog.csdn.net/cslbupt/article/details/65935577

https://blog.csdn.net/sky_100/article/details/77675792?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.control&dist_request_id=&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.control