Understanding Comparator in Java PriorityQueue

Question

I have the following code:

   HashMap<Character, Integer> charCount = new HashMap<Character, Integer>();
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        charCount.put(c, charCount.getOrDefault(c, 0) + 1);
    }
    
    PriorityQueue<Character> maxHeap = new PriorityQueue((a, b) -> charCount.get(b) - charCount.get(a));

maxHeap.addAll(charCount.keySet());

The maxHeap clearly sorts the elements to be from highest frequency to lowest but I don't understand that comparator function. I find the syntax here (a, b) -> charCount.get(b) - charCount.get(a) to be quite confusing and I was hoping someone could walk through how this actually compares the elements to sort them into this maxHeap. Thanks!

rzwitserloot · Accepted Answer · 2020-11-15 18:36:55Z

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

is so-called lambda syntax. It's syntax sugar* for this:

new Comparator<Character>() {
    public int compare(Character a, Character b) {
        return charCount.get(b) - charCount.get(a);
    }
}

Which in turn is syntax sugar for:

class MyCharacterComparator implements Comparator<Character> {
    public int compare(Character a, Character b) {
        return charCount.get(b) - charCount.get(a);
    }
}
PriorityQueue<Character> maxHeap = new PriorityQueue(new MyCharacterComparator());

But it all boils down to the same thing: It represents the concept of charCount.get(b) - charCount.get(a). Not the result of that calculation, but the calculation itself. You hand the calculation as a concept to PriorityQueue's constructor, and then PriorityQueue will invoke this code as many times as it wants, passing in whatever it needs in order to do the job.

In this situation, charCount maps a given character to how often that character shows up in String s. The comparator will then retrieve the 'frequency' (or character count) of the second argument and the first argument, and then calculates the difference (count(b) - count(a)). The comparator method is specced to work as follows: If the result is negative, then 'a' is before 'b'. If it is positive, then 'a' is after 'b'. If it is equal, than 'a' and 'b' compare on equal footing.

Thus, if the character of variable 'b' occurs, say, 10 times, and the character of variable 'a' occurs, say, 8 times, then you calculate 10 - 8, which is a positive number, which implies that 'b' is considered to sort before a (sorts earlier; is lower).

Thus, it prioritizes characters that appear more often.

*) Not entirely; inspect the class file with e.g. javap and you'll find that it ends up differently, and there are also a few other differences. But it's almost the same thing.

Collectives™ on Stack Overflow

Understanding Comparator in Java PriorityQueue

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related