Home > Blockchain >  What does this priority queue condition in java mean?
What does this priority queue condition in java mean?

Time:12-02

I happen to encounter this line of java

PriorityQueue<Integer> pq = new PriorityQueue<>((num1, num2) ->
                                hashMap.get(num1)-hashMap.get(num2));

I have done a lot of googling but couldn't find anything clear. According to my understanding, I am using my custom function to create a priority queue in which we are comparing two numbers based on values present in hashMap. The number which has the smallest value in the hashMap will be at the top of the priority queue. Am I correct? What does this line exactly do:

hashMap.get(num1)-hashMap.get(num2)

What I don't understand, the comparator should be boolean but hashMap.get(num1)-hashMap.get(num2) will give an integral value. If it is 0, then it will be equal to false and if it is non-zero it will be equal to true, right? Whereas we want values less than or equal to 0 to be true

CodePudding user response:

Yes you are correct.

The line hashMap.get(num1)-hashMap.get(num2) just does a substraction as you'd expect it to.

The key here is that a comparator function is just a function that returns an integer: positive/zero/negative depending on whether first argument is greater/equal/lower compared to second.

CodePudding user response:

With simple words, PriorityQueue is a sorted array, and in the constructor, you can (optionally) provide a Comparator to tell the queue how to sort the elements.

hashMap.get(num1) - hashMap.get(num2) is a Comparator. You can see, that given numbers is just a keys and take its values.

int res = hashMap.get(num1) - hashMap.get(num2);

  • res < 0: place num1 before num2
  • res >= 0: place num1 after num2

CodePudding user response:

This creates a priority queue of integer keys ordered by associated values that come from hashMap. The priority queue is not ordered by the data in the queue itself, the values in the queue are keys that are used to look up values in the hash map and the queue is ordered by those values. Such techniques are sometimes used instead of creating a new class that holds the key and value together and implements the Comparable interface by comparing the values (possibly using the subtraction trick).

a - b (or b - a, depending on which order you want) is slightly sneaky a way to implement a comparator function when the inputs are integers. This works because any negative result is interpreted as "smaller than", not only -1, and any positive result is interpreted as "greater than", not only 1. A comparator function is not supposed to return a boolean as you suggest, it's supposed to work like this:

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

There is a condition for using this trick: it only works if the magnitudes of the values are small enough that overflow never occurs. This compare-by-subtract trick is not reliable if you do not know that all your values are sufficiently small.

  • Related