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

Question

假设我有一个列表包含：

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

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

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

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

[10,8,5,4]

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

Answer 1

log K 项表示您只需要 K 大小的堆。这是一种可能的解决方案。

从未排序的数组开始。将前 K 个元素转换为大小 K 的 min-heap。堆的顶部是最小的元素。在 O(log K) 时间内，用数组中剩余的每个 N - K 元素（不构成堆的一部分）连续替换最小元素。在 O(N) 此类操作之后，数组中的第一个 K 元素（或者，您创建的堆的 K 元素）现在将拥有数组中最大的 K 个元素.

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

Answer 2

 PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    for (int i : your_arraylist){
       pq.add(i);  //add to queue

      if(pq. size() > k){
         pq.poll();   //remove the top element, smallest in this case, once the queue 
                     // reaches the size K
       }
    }
System.out.println(pq);

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

Find the top K elements in O(N log K) time using heaps

algorithm

heap

heapsort