Understanding PriorityQueue Comparator syntax in Java

1. A constructor call to PriorityQueue accepts a Comparator.

new PriorityQueue<>((a,b) -> map.get(b) - map.get(a));

2. Comparator is defined as a FunctionalInterface.

This is a functional interface and can therefore be used as the assignment target for a lambda expression or method reference.

3. The abstract method of the functional interface is,

int compare(T o1, T o2)

...where T is the type within the queue, in this case, Integer. In other words, the method requires two arguments of the same type as input and produces an int as output (note: this is the same general method shape as a BiFunction or ToIntBiFunction).

4. The lambda expression provided is,

(a,b) -> map.get(b) - map.get(a)

...which satisfies the abstract method signature as,

(Integer a, Integer b) -> map.get(b) - map.get(a)

...by looking up the (Integer) values corresponding to both a and b in the previously-instantiated HashMap and subtracting one Integer from the other to return an int. Subtraction results in the higher value being "prioritized".

5. This implementation assumes every Integer added to the queue has already been added as a key in the map, with a corresponding, non-null value; otherwise, the Comparator throws a NullPointerException.

If the result of map.get(b) - map.get(a) is positive, which means that b has a higher frequency than a. In the context of a PriorityQueue, this means that b should be prioritized (or placed higher in the heap) than a.

If the result is negative, a has a higher frequency than b, so a should be prioritized.

If the result is zero, they have the same frequency, and their order is not changed relative to each other (but in the max heap, one will still take precedence over the other based on their insertion order).

The constructor is declared as PriorityQueue(Comparator<? super E> comparator), since Comparator is a functional interface, the lambda expression (a,b) -> map.get(b) - map.get(a) is creating an anonymous Comparator similar to:

new Comparator<Integer>() {

    @Override
    public int compare(Integer a, Integer b) {
        return map.get(b) - map.get(a);
    }
}

^{Note 1: but no class (.class file) is created, as would be the case for an anonymous class}
_{Note 2: as mentioned multiple times, comparing int values using subtraction can lead to errors (overflow/underflow);
it is recommended to use the static Integer.compare() method instead}

Queue heap = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));

creates a max-heap PriorityQueue where the priority is determined by the values associated with each integer in the map. The comparator (a, b) -> map.get(b) - map.get(a) ensures that the element with the higher value in the map comes first in the queue. This way, the queue prioritizes elements based on their associated values in descending order.