algorithm - 使用堆在 O(N log K) 时间内找到前 K 个元素

Question

假设我有一个包含以下内容的列表:

lst = [4,0,8,3,1,5,10]

并且我计划使用堆结构来帮助我检索前 k 个最大的数字，其中 k 是用户输入。

我知道堆排序是 O(N log N)，我们首先用 O(N) 的时间将它们放入最小/最大堆中，然后用 O(log N) 的时间检索元素。

但我现在面临的问题是，我需要在 O(N log K) 时间内检索前 k 个用户。如果我的 k 是 4，我会:

[10,8,5,4] 

作为我的输出。我感到困惑的是，在形成堆的早期阶段，我是否应该将整个列表堆起来以检索前 k 个元素？

Answer 1

log K 术语表明您只需要一个大小为 K 的堆。这是一种可能的解决方案。

从一个未排序的数组开始。将前 K 元素转换为大小为 K 的最小堆。堆的顶部是最小的元素。在 O(log K) 时间内用数组中剩余的 N - K 个元素(不构成堆的一部分)依次替换最小元素.在 O(N) 这样的操作之后，数组中的前 K 元素(或者，您创建的堆的 K 元素)现在将数组中有 K 个最大的元素。

还有其他解决方案，但这是最直接的。