CODEWITHSUNDEEP
javadata-structurespriority-queue
DChalo123
DChalo123

Reputation: 165

Can someone explain PriorityQueue in this example to me?

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.

Upvotes: 4

Views: 2682

Answers (2)

ricky3350
ricky3350

Reputation: 1738

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!

Upvotes: 8

ernest_k
ernest_k

Reputation: 45309

The PriorityQueue constructor you're using is declared as:

public PriorityQueue(Comparator<? super E> comparator)

It takes a comparator of object of the generic type argument. The comparator constructor parameter is described as:

the comparator that will be used to order this priority queue. If null, the natural ordering of the elements will be used.

In your call, the argument is a lambda expression that provides implements Comparator<String>. It's roughly equivalent to the following anonymous class:

PriorityQueue<String> heap2 = new PriorityQueue<String>(new Comparator<String>() {
    @Override
    public int compare(String w1, String w2) {

        if(count.get(w1).equals(count.get(w2))) {
            return w2.compareTo(w1);
        } else {
            return count.get(w1) - count.get(w2);
        }

        // can also just be (without the if/else above):
        //return count.get(w1).equals(count.get(w2)) ? w2.compareTo(w1) : count.get(w1) - count.get(w2);
    }
});

Upvotes: 3

Related Questions