How does this Lambda expression in Java help in sorting ? help me understand

Question

The task here is that i get input string, for example 'tree' and sort it based on frequency, Output should be 'eetr'/'eert', since e repeats 2 times and t,r frequency is 1.

i have this code, what is does it traverses the string, puts all characters in string in Hashmap with their frequencies and a priority queue is used for sorting them in descending order, after which the result is taken in a string builder,

but i need some help in understanding the lambda function used in the parameter of priority queue. Here is my function.

public String frequencySort(String s)          // lets assume that input string is "tree"
{
    HashMap<Character,Integer> map = new HashMap<>();
    for(char c:s.toCharArray())
    {
        map.put(c,map.getOrDefault(c,0) + 1);
    }                                                       //  now after this my HashMap will have values (t,1),(r,1),(e,2)

PriorityQueue<Character> maxHeap = new PriorityQueue<>((a,b) -> map.get(b) - map.get(a));  //my question is about this constructor in priority queue, There are just two input parameters , how subtracting two things will help in sorting ??

maxHeap.addAll(map.keySet()); // i guess the keyset is now 't,r,e'  but constructor has only 2 parameters, what is going on ? How will the constructor help in setting the sorting behaviour of prioroty queue? 

StringBuilder result = new StringBuilder();

    while(maxHeap.isEmpty())
    {
        char current = maxHeap.remove();
        for(int i=0;i < map.get(current);i++)
        {
            result.append(current);
        }
    }

}

can someone explain me the flow using example 'tree' in the function

Answer 1

but constructor has only 2 parameters

No, look carefully, in new PriorityQueue(...), the ... part contains only one thing - (a, b) -> map.get(b) - map.get(a). PriorityQueue<Character>'s constructor expects one argument of type Comparator<Character>. A Comparator is an object that is able to compare two objects and tell which is "greater", or whether they are equal. The priority queue will use this Comparator to order its elements.

If you find the lambda expression confusing, how about rewriting the code to:

new PriorityQueue<>(Comparator.comparing(map::get).reversed());

The intent should be clearer, and it does roughly the same thing. We are creating a priority queue that should compare its elements by comparing the integers we get by applying map.get on each of them. In other words, given two elements a and b, the queue should decide which element comes first by comparing map.get(a) and map.get(b). And you want the reverse ascending (i.e. descending) order.

In your original code, rather than using the comparing method which returns a Comparator<Character>, it is using a lambda expression which is basically the implementation of the compare method. If you read the documentation for that method, you will see that you should:

• return a negative integer if the first argument is "smaller" than the second
• return 0 if the arguments are equal
• return a positive integer if the first argument is "greater" than the second

Observe that mathematically, if map.get(a) < map.get(b), map.get(a) - map.get(b) will be negative. If map.get(a) > map.get(b), map.get(a) - map.get(b) will be positive, and if map.get(a) = map.get(b), map.get(a) - map.get(b) will be 0.

Now you should see why map.get(b) - map.get(a) gives you the reverse order by comparing the integers got by applying map.get to each element.

Miscellaneous notes:

• Using subtraction to implement Comparator is not actually a good idea, because overflow. See here for more info.
• Your code has two typos/mistakes. 1. missing a return result.toString(); statement at the end 2. the loop control condition should be while(!maxHeap.isEmpty()). You missed a !.

Answer 2

It's very similar to wordCount example in Scala. But it counts words in a string but your program counts letters in a word. very similar.

However, the map output will be as follow:

(t,1), (r,1), (e,2)

The map.get(b) - map.get(a) is just used as comparator. If map.get(b) - map.get(a) be negative which means map.get(b) < map.get(a) and results to order before a. If be positive means map.get(b) > map.get(a) and results to order after a. If be zero, they are equal.

See Javadoc for PriorityQueue : An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

Answer 3

The use of "implicit" comparators like this has, I think, the potential to be very confusing. The PriorityQueue constructor (since Java 8) is defined to take a java.util.Comparator for one it arguments. The Comparator interface specifies a function compare() that takes two arguments, and returns an integer. The sign of the integer indicates which of the elements is the larger. That's why, in the OP, the values of the two elements are subtracted -- if the are equal, the result will be zero. If one is larger than the other, the result will be either positive or negative. The PriorityQueue implementation uses these results, applied to many elements, to determine the order they should be placed in.

This logic was, I think, fairly intuitive before lamba expressions came on the scene. Now, Comparator is declared to be a "functional interface". That means an anonymous instantiation of the interface can be created directly from a lamba expression. the Java compiler knows that the argument to the PriorityQueue constructor is a Comparator, and it knows to instantiate a Comparator based on the lambda expression. The lambda expression takes two arguments, a and b in this case. The Comparator interface has a method that takes two arguments -- compare (a,b). Hence there is a match that can be used in code generation.

So Java generates code that replaces the lamba expression with a definition of a Comparator whose compare (a,b) method is the implementation of the lambda function (that is, the text to the right of the ->).

What makes this potentially confusing, I think, is that the Comparator interface itself is completely invisible -- you need to know that PriorityQueue has a Comparator argument, and that Comparator is a functional interface that has one method with two arguments, compare(), that matches the lamba expression.