资料来源：维基百科
使用堆或其他优先级队列数据结构，也可以进行流式单遍部分排序。首先，将输入的前k个元素插入结构中。然后遍历其余元素，依次将每个元素添加到结构中，并删除最大的元素。每次插入操作还需要O（log k）时间，因此总共需要O（n log k）时间。
make one pass over the remaining elements, add each to the structure in turn, and remove the largest element。这与1）中描述的方法不一样吗？建议的方法是流式传输。考虑到空间复杂度为O（k），它不需要将所有项目都存储在内存中即可运行heapify算法（但它只能找到前k个项目）。
该算法的更明确的描述（另请参见WP提供的参考）是
通过构造，堆永远不会增长到超过k + 1个元素。可以从磁盘，通过网络等流式传输项目，而使用heapify算法则无法实现。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句