使用堆在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最大的元素。

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

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);