部分排序以找到第k大/小的元素

Question

来源： 维基百科

使用堆或其他优先队列数据结构也可以实现流式单次部分排序。首先将输入的前k个元素插入该结构中，然后在剩余的元素上进行一次遍历，依次将每个元素添加到结构中并删除最大的元素。每个插入操作的时间复杂度也为O(log k)，总的时间复杂度为O(n log k)。

1. 这与我们先对完整的输入数组进行堆化（O(n)时间），然后从堆中抽取k次最小值有何不同？
2. 我不理解它说要“对剩余元素进行一次遍历，依次将每个元素添加到结构中并删除最大的元素”那部分。这不与1）中描述的方法相同吗？

- Dubby

Answer 1

建议的方法是流式处理。它不需要将所有项目存储在内存中以运行堆化算法，因为它具有O(k)的空间复杂度（但它只能找到前k个项目）。

算法的更明确描述（也可以参见reference WP）如下：

- 给定一系列项目： - 对于流中的前k个元素创建一个堆， - 对于第k个元素之后的每个元素： - 将其推入堆中， - 提取最大（或最小）元素并丢弃它， - 最后返回堆中剩余的k个值。

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

- Fred Foo

---

所以基本上这种方法在我们有限的内存时很有用？还有其他好处吗？ - Dubby

就是这样。请参阅幻灯片：“除非m很小或在在线设置中使用，否则不太吸引人”。 - Fred Foo

+1。好答案。一个明显的优化是只有在它比堆上已经存在的最小项更大时才将该项添加到堆中（如果你正在寻找k个最大项）。由于Peek是O(1)操作，这证明非常有效。 - Jim Mischel