资料来源:维基百科
使用堆或其他优先级队列数据结构也可以进行流式单遍部分排序。首先,将输入的前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] 删除。
我来说两句