CODEWITHSUNDEEP
javaalgorithmpriority-queue
Altaf
Altaf

Reputation: 429

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

I am trying to find the smallest kth value for an array. I used a priorityQueue data structure to remove values that are greater than k, but I am returning an incorrect result. My code is below:

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

How can I fix the algorithm to return the correct result?

Upvotes: 1

Views: 68

Answers (1)

trincot
trincot

Reputation: 350477

You did not create a Max Heap, but a Min Heap. To create a Max Heap you need to pass a comparator to the PriorityQueue constructor:

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

Upvotes: 2

Related Questions