java priority queue doesn't get correct order based on the frequency of hashmap

user_10155556 0
Viewed 255
       Map<Integer, Integer> map = new HashMap<>();
        
        for (int n : arr) map.put(n, map.getOrDefault(n, 0) + 1);

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for (int n : arr) pq.add(n);
        
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }

Assume the input arr is [4,3,1,1,3,3,2,2] and after we put them all inside the pq and poll them one by one. the correct order should be 4 1 1 2 2 3 3 3 in the order of frequency.

But the output order is 4 1 2 2 1 3 3 3 which didn't output the correct order.

priority-queue hashmap java
3 Answers

The order is correct. PriorityQueue doesn't guarantee how ties are broken, and 1 and 2 are tied:

If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.

If you want to pick an order for ties, then your comparator should do that. The easiest way is to write Comparators.comparingInt(i -> map.get(i)).thenComparingInt(i -> i) to break ties in ascending order.

user_8697360

Both 1 and 2 appear twice in the array, so as far as the priority queue is concerned, they are "equal", as you are just telling the priority queue to compare their frequency only. Since they are equal, they can appear in any order.

So to fix this, you need to tell the priority queue what to do when the elements are equal. Although you could try to add this logic to your lambda, this can be more easily done with a comparing and thenComparing call:

PriorityQueue<Integer> pq = new PriorityQueue<>(
    Comparator.<Integer, Integer>comparing(map::get)
        .thenComparing(Function.identity())
);

This means "compare the value you get from the map, then compare the number itself". This means that it will order 1 before 2, even if both 1 and 2 occurred twice.

user_51335850

Simpler way to achieve the same-

PriorityQueue<Map.Entry<Integer,Integer>> pq=new PriorityQueue<>(a,b) -> map.get(a)==map.get(b) ? b-a: map.get(b)-map.get(a));

Here you first check if the map value for the respective key are same or not if same then sort on the basis of the key

if not same then simply sort on the basis of frequency

user_195518140
Related