Priority Queue in Java (Max Heap declaration)

Question

I wish to make a max heap in Java,but couldn't understand this. can someone explain this to me

Question: Given a string, sort it in decreasing order based on the frequency of characters.

Input="tree"

Output Expected:"eetr"

So I need a max heap using Priority Queue,but i didn't get how this code works. How the declaration of Priority Queue works?

    public class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);

        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        pq.addAll(map.entrySet());

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Map.Entry e = pq.poll();
            for (int i = 0; i < (int)e.getValue(); i++) 
                sb.append(e.getKey());
        }
        return sb.toString();
    }
}

so want to know how this

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

thing works for making a Priority Queue.

Does this answer your question? [Why can a lambda expression be used as a Comparator?](https://stackoverflow.com/questions/43866032/why-can-a-lambda-expression-be-used-as-a-comparator) — Progman, Mar 27 '20 at 22:28

Jim Mischel · Answer 1 · 2023-01-31T05:52:08.133

You got your answer in a comment, which explains what's happening in that constructor call. I want to explain why the expression b.getValue() - a.getValue() should not be used as a comparison function.

Just to review, the reason that expression appears to work is because the semantics for the comparator is such that, when it's called with (a,b), then:

If the result is < 0, then a < b
If the result is 0, then a == b
If the result is > 0, then a > b

So, given two integers, then compare(a, b) becomes result = a - b, and obviously that works. Or at least it works for the simple cases that most people will test.

But most people don't test for integer overflow. Imagine that

a = INTEGER.MAX_VALUE;
b = -1;

Now you have a problem. The expression a - b results in integer overflow, and the result is INTEGER.MIN_VALUE. So it erroneously reports that INTEGER.MAX_VALUE is smaller than -1.

Any time that a is sufficiently positive and b is sufficiently negative to cause an integer overflow, using subtraction as a substitute for comparison will give you erroneous results. This is also true if a is sufficiently negative and b is sufficiently positive.

The correct way to compare is use the comparison method. For example:

a.getValue().compareTo(b.getValue())

In your particular case, this isn't a problem because your counts won't go negative. In fact, in most cases I've seen, this won't be a problem because most usages don't have negative numbers or the numbers just aren't large (or small) enough. But that's not the real point.

The real point is that using a - b in place of comparison is an old optimization trick that people still employ today without thinking through the ramifications of doing so. And, although it is faster than calling compareTo, the difference is irrelevant in most applications. And it exposes your code to the risk I mention above. It's not a good practice to fall into.

As I've said in the past, "Doing something stupid to save a few nanoseconds is just stupid."

Priority Queue in Java (Max Heap declaration)

1 Answers1