搜索最小 k 值的 PriorityQueue 算法返回不正确的结果

Question

我正在尝试为数组找到最小的第 k 个值。我使用了 priorityQueue 数据结构来删除大于 k 的值，但我 return 结果不正确。我的代码如下：

public class Main2 {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>();
    
    public int smallestK(int[] arr, int k) {
        
        for(int num : arr) {
            maxHeap.add(num);
            if(maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        return maxHeap.peek(); 
    }
    
    public static void main(String[] args) {
        int arr[] = { 12, 3, 5, 7, 4, 19, 26 };
        
        Main2 smallest = new Main2();
        int result = smallest.smallestK(arr, 3); //should return 5, but returns 12
        System.out.println(result);
    }
}

我怎样才能将算法修正为 return 正确的结果？

Answer 1

您创建的不是最大堆，而是最小堆。要创建最大堆，您需要将比较器传递给 PriorityQueue 构造函数：

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());

搜索最小 k 值的 PriorityQueue 算法返回不正确的结果

PriorityQueue algorithm searching for the smallest k value is returning incorrect result

java

algorithm

priority-queue