algorithm - 部分排序以找到第 k 个最大/最小元素

Question

来源:Wikipedia

A streaming, single-pass partial sort is also possible using heaps or other priority queue data structures. First, insert the first k elements of the input into the structure. Then make one pass over the remaining elements, add each to the structure in turn, and remove the largest element. Each insertion operation also takes O(log k) time, resulting in O(n log k) time overall.

1. 这与我们首先在 O(n) 时间内堆化完整的输入数组然后提取堆中的最小值 k 次的情况有何不同。
2. 我不明白它说遍历剩余元素，依次将每个元素添加到结构中，然后删除最大元素 的部分。这不是和1)中描述的方法一样吗？

Answer 1

建议的方法是流式传输。考虑到 O(k) 空间复杂度(但它只会找到前 k 个项目)，它不需要内存中的所有项目来运行 heapify 算法。

算法的更明确的描述(另请参阅 WP 给出的 reference)是

• 给定一个项目流:
• 将流中的前 k 个元素堆成一个堆，
• 对于第一个 k 之后的每个元素:
  • 将其压入堆中，
  • 从堆中取出最大(或最小)的元素并丢弃，
• 最后返回堆中剩余的 k 个值。

通过构建，堆永远不会增长到超过 k + 1 个元素。这些项目可以从磁盘、网络等流式传输，这对于 heapify 算法是不可能的。