PriorityQueue算法搜索最小k值返回错误结果

Question

我试图找到数组的最小第k个值。我使用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);
    }
}

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

Answer 1

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

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