部分排序以查找第k个最大/最小元素

Question

资料来源：维基百科

使用堆或其他优先级队列数据结构也可以进行流式单遍部分排序。首先，将输入的前k个元素插入结构中。然后遍历其余元素，依次将每个元素添加到结构中，并删除最大的元素。每个插入操作还需要O（log k）时间，因此总共需要O（n log k）时间。

1. 这与我们先在O（n）时间内对整个输入数组进行堆放，然后提取k次最小堆的情况有何不同？
2. 我不明白该说什么make one pass over the remaining elements, add each to the structure in turn, and remove the largest element。这与1）中描述的方法不同吗？

Answer 1

建议的方法是流式传输。考虑到空间复杂度为O（k），它不需要将所有项目都存储在内存中即可运行heapify算法（但它只会找到前k个项目）。

该算法的更明确描述（另请参见WP提供的参考）是

• 给定一个项目流：
• 在流中的前k个元素中堆积一堆，
• 对于第一个k之后的每个元素：
  • 把它推到堆上
  • 从堆中提取最大（或最小）元素并将其丢弃，
• 最后返回堆中剩余的k个值。

通过构造，堆永远不会增长到超过k + 1个元素。可以从磁盘，网络等流式传输项目，而使用heapify算法则无法实现。