使用堆在 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。在堆的顶部将是您最小的元素。及时用N - K数组中剩余的每个元素（不构成堆的一部分）依次替换最小元素O(log K)。在O(N)这些操作之后，K数组中的第一个元素（或K您创建的堆的元素）现在将拥有K数组中最大的元素。

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