Can someone explain PriorityQueue in this example to me?

Question

I am trying to learn how to use a PriorityQueue, as I have never used one before. Here is an example of one in use that I have found on LeetCode for a problem that finds the Top K elements in an array of strings

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap();
    for (String word: words) {
        count.put(word, count.getOrDefault(word, 0) + 1);
    }
    PriorityQueue<String> heap = new PriorityQueue<String>(
            (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
            w2.compareTo(w1) : count.get(w1) - count.get(w2) );

    for (String word: count.keySet()) {
        heap.offer(word);
        if (heap.size() > k) heap.poll();
    }

    List<String> ans = new ArrayList();
    while (!heap.isEmpty()) ans.add(heap.poll());
    Collections.reverse(ans);
    return ans;
}

More notably I would like to know what this line is doing:

PriorityQueue<String> heap = new PriorityQueue<String>(
            (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
            w2.compareTo(w1) : count.get(w1) - count.get(w2) );

Can someone explain in lame-man's terms what is happening here? Is there any way to rewrite the comparater as a regular "if" statement?

Thanks for any help.

Answer 1

The expression you have in the constructor is a lambda expression. Because Comparator is a functional interface, that is, it's an interface with only one abstract method, a lambda expression can be used as shorthand for creating an anonymous class.

In your example,

new PriorityQueue<String>((w1, w2) -> count.get(w1).equals(count.get(w2)) ? w2.compareTo(w1) : count.get(w1) - count.get(w2));

is functionally equivalent to

new PriorityQueue<String>(new Comparator<String>() {
    public int compare(String w1, String w2) {
        return count.get(w1).equals(count.get(w2)) ? w2.compareTo(w1) : count.get(w1) - count.get(w2);
    }
});

This would also be the same as making a separate class that implements Comparator<String>, and passing an instance of that class as the parameter to the PriorityQueue.

As for writing the Comparator as an if statement, the short answer is, no. The comparator has to be an instance of Comparator<String>. However, perhaps a more understandable version of the same comparator is as follows:

new PriorityQueue<String>((w1, w2) -> {
    if (count.get(w1).equals(count.get(w2))) { // If the counts of w1 and w2 are the same,
        return w2.compareTo(w1); // Then return the reverse lexicographical ordering of w1 and w2 (e.g. "Zebra" comes before "Apple")
    } else if (count.get(w1) < count.get(w2)) {
        return -1; // w1 comes before w2
    } else {
        return 1; // w1 comes after w2
    }
});

Note: "Lexicographical ordering" is essentially alphabetical ordering, but based on ASCII codes. For more information, see String#compareTo(String)

Hope this helps!