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

Question

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

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

如何修复算法以返回正确的结果？

标签： javaalgorithmpriority-queue

Answer 1

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

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