Priority Queue is not returning proper value according to priority in Java

Question

I have an array where I have to get the highest k frequent integers from the array.

int[] nums = new int[] {5,3,1,1,1,3,73,1};
int k  = 2

My Function looks like this:

static public List<Integer> topKFrequent(int[] nums, int k) {
    List<Integer> res = new ArrayList<>();
    if (nums.length == 0)
        return res;
    Map<Integer, Integer> hash = new HashMap<>();
    for (int i : nums) {
        hash.put(i, hash.getOrDefault(i, 0) + 1);
    }

    System.out.println(hash);

    Queue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<> (
            (a, b) -> a.getValue() > b.getValue()? a.getValue():b.getValue()
    );
    for (Map.Entry<Integer, Integer> entry : hash.entrySet()) {
        pq.offer(entry);
    }

    System.out.println(pq);

    System.out.println(pq.poll());
    System.out.println(pq.poll());

//  for (int i=0; i<k; i++)
//      res.add(pq.poll().getKey());

    return res;
}

But when I am printing the top 2 elements from the priority queue, I am getting: Output:

{1=4, 3=2, 5=1, 73=1} // hash map output
[1=4, 3=2, 5=1, 73=1] // complete priority queue output
1=4 // first poll from priority queue
5=1 // second poll from priority queue

The second item is returned wrong, it should have been 3=2. Can anyone please tell me what is wrong with the code? Is the comparator not correct?

Answer 1

Problem is with your comparator's compare method. Compare method contract is

1. if a less than b return negative integer.
2. if a greater than b return positive integer.
3. if a equals b then return 0.

try below code

static public List<Integer> topKFrequent(int[] nums, int k) {
    List<Integer> res = new ArrayList<>();
    if (nums.length == 0)
        return res;
    Map<Integer, Integer> hash = new HashMap<>();
    for (int i : nums) {
        hash.put(i, hash.getOrDefault(i, 0) + 1);
    }

    System.out.println(hash);


    Queue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<> (
            (a, b) -> Integer.compare(b.getValue(), a.getValue())
    );
    for (Map.Entry<Integer, Integer> entry : hash.entrySet()) {
        pq.offer(entry);
    }


    for (int i = 0; i < k; i++) {
        res.add(pq.poll().getKey());
    }
    return res;
}