Cannot understand how PriorityQueue gets ordered using a Comparator

[Sandra Bachan]

Cannot understand how PriorityQueue gets ordered using a Comparator.


According to API for Comparator, it says:

int compare(T o1, T o2)
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.

Below is code based on Chapter 7, Sierra/Bates:

import java.util.*;
class PQ{
	static class PQsort implements Comparator<Integer>{	// inverse sort
		public int compare(Integer one, Integer two){
			return two - one;			// unboxing
		}
	}
	public static void main(String[] args){
		int[] ia = {1,5,3,7,6,9,8};			// unordered data
		PriorityQueue<Integer> pq1 = 
			new PriorityQueue<Integer>();		// use natural order
		
		for (int x : ia)				// load queue
			pq1.offer(x);
			
		for (int x : ia)				// review queue
			System.out.print(pq1.poll() + " ");
		System.out.println("");
			
		PQsort pqs = new PQsort();			// get a Comparator
		PriorityQueue<Integer> pq2 = 
			new PriorityQueue<Integer>(10,pqs);	// use Comparator
			
		for (int x : ia)				// load queue
			pq2.offer(x);
		
		
		for (int x : ia)				// review queue
			System.out.print(pq2.poll() + " ");
		
		System.out.println(" ");
	}
}

Below is the output:
1 3 5 6 7 8 9
9 8 7 6 5 3 1

I am unable to trace the logic of this code because I cannot grasp how Comparator works. Why does code in PQsort return two-one? When I change the code such that it returns two, I get the following output:

1 3 5 6 7 8 9
1 3 9 8 6 5 7

[Henry Wong]

Sandra Bachan wrote:
According to API for Comparator, it says:

int compare(T o1, T o2)
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.

class PQ{
	static class PQsort implements Comparator<Integer>{	// inverse sort
		public int compare(Integer one, Integer two){
			return two - one;			// unboxing
		}
	}
}

I am unable to trace the logic of this code because I cannot grasp how Comparator works. Why does code in PQsort return two-one?

There is, at least, two tricks being played here. They are both somewhat confusing, so may be hard to grasp at the same time.

First take a look at this code... comparator for natural ordering...

class PQ{
	static class PQsort implements Comparator<Integer>{	// natural order sort
		public int compare(Integer one, Integer two){
			return one - two;			// unboxing
		}
	}
}

If one is less than two, doesn't "one - two" yield a negative number?

if one is equal to two, doesn't "one - two" yield a value of zero?

if one is greater than two, doesn't "one - two" yield a positive number?

So... using a simple trick of subtracting the second parameter from the first parameter, we are about to satisfy the return values for the comparator, without using a long list of "if-then" instructions. Pretty cool trick huh?


Next... what if you want to reverse the order of the sort? Meaning what if you want the bigger number to come first? One way to do it is to reverse the comparator -- meaning to return the opposite of the comparison. If the first number is bigger, to return that it is actually smaller, and vice-versa.

So... instead of returning a negative number, return a positive number. And instead of returning a positive number, to return a negative number.

So... instead of returning "one - two", you return the negative of "one - two", which if you work out the math, works out to "two - one".

Another cool trick, huh?


Henry

[Mohit G Gupta]

THe line 21-22 says :

  PriorityQueue<Integer> pq2 =   
             new PriorityQueue<Integer>(10,pqs);   

can anyone explain how does the above code works .
i know the following code to sort PriorityQueue

  

 PriorityQueue<Integer> pq2 =   
             new PriorityQueue<Integer>();
Collections.sort(pq2,pqs)

  

[Chad Michaels]

Hello Sandra,

Well, there's obviously a million people on this site who are more qualified to answer this question, but I'll give it a shot since I understand exactly where you're coming from.

Forget everything you know about the compare( ) and just know this... it returns an int, and it takes two parameters. For example, let's say... compare( Car , Car ). When you look at the parameter list of this method, it's obvious that one car is the "first" parameter, and the other car is the "second" parameter, right? I mean, that's the only possibility. Anyway, if we invoked compare( redCar , greenCar ), we can say redCar is the first argument and greenCar is the second argument. Easy enough, right?

Well, the way I see the compare( ) is like this... if the integer value returned is negative, no matter how it was calculated, the "first" parameter in the parameter list will be placed (sorted) before the whatever object is the second parameter in the parameter list. And conversely, if the integer value returned is positive, the "second" parameter is placed before the "first" parameter. For example, if my compare( Car , Car ) simply returned the constant (-1) on every invocation, then every car listed as the first argument of the method will always be sorted before whatever car is listed as the second argument.

So my advice is to first look at the calculation of the return value to see if it returns pos/neg/zero. Then, glance at the method call, and you'll see what comes before/after. Let's look at your example again....

public int compare( Integer one , Integer two ){
return two - one ; // unboxing
}

Try not to get caught up in the words "one" and "two", and just follow the rules. Based on the above return value, it looks like if you passed ( 3 , 5 ) into that compare method, you'll get +2 because ( 5 - 3 ). Because that is positive, this means the second argument (5) comes before the first argument (3); hence, the sort is ordered from large to small because 5 will come before 3.

If, for example, the above method's return value was return( one - two ), and the same arguments of ( 3 , 5 ) were passed, it would return -2 because ( 3 - 5 ), which would then mean the sort is ordered from least to greatest because the first argument comes before the second argument.

Remember: If it returns a negative value, whatever the first argument is will be placed (sorted) before the 2nd argument. If it returns pos, whatever the 2 arg is will be listed before the 1st arg.

Again, maybe I'm way off here, but that's just how I see it. Hope that helped somehow.

[Sandra Bachan]

@ Chad: Wow, that was descriptive and quite helpful. It definitely re-enforces and provides a clearer picture as to how comparator works.

Thank you all!

[Katherine Reut]

Mohit G Gupta wrote:THe line 21-22 says :

  PriorityQueue<Integer> pq2 =   
             new PriorityQueue<Integer>(10,pqs);   

can anyone explain how does the above code works?

I had the same question, and I finally looked at PriorityQueue's javadocs to (sort of) figure it out.

The above PriorityQueue has two parameters. The first parameter, 10, is the initial capacity of the PriorityQueue. The second paramater, pqs, is the comparator to be used. In this case, the comparator to be used is PQsort, which sorts elements in reverse natural order.

In contrast, on lines 10 and 11:

  PriorityQueue<Integer> pq2 =   
             new PriorityQueue<Integer>();   

The above PriorityQueue has a null comparator, so the natural ordering of the elements will be used (i.e. An entry of "1" has higher priority than an entry of "2" as said on page 591).

So MY question is, the PQsort comparator works as Chad and Henry explained, but I am still unsure about where the comparator actually arranges the elements into the sorted order. Is it on line 13 and 14, when the queue is loaded? But then in the comparator, what are the values of the first and second parameters? Where do they come from? Is the first parameter (Integer one) the value of "x" in the for-each loop, and the second parameter (Integer two) the value of the last element added to pq2?

[Nick Widelec]

Sandra Bachan wrote:
Cannot understand how PriorityQueue gets ordered using a Comparator.


According to API for Comparator, it says:

int compare(T o1, T o2)
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.

Below is code based on Chapter 7, Sierra/Bates:
...

Hi Sandra,



Regarding to how comparator works you could try to add swap the second for each loop with:

new PriorityQueue<Integer>(10,pqs);   // use Comparator  
            for (int x : ia) 
            {// load queue  
                pq2.offer(x);
                if (pq2.size()==2)
                {
                	System.out.println(pq2);
                }

So you can see what happen when only the first two elements are compared: Integer "one" (1) and Integer "two" (5), the comparator gets called when you insert the second element, which gives the following result two-one hence 5-1 =4. Positive number means the first Object inserted in the compare method (in this case Integer one), will be greater than the second Object inserted in the method as an argument (Integer two).
so the comparator does: running the compare(one, two) method... 5-1 = 4 positive number.. one> two (independently from what value the Integer has, otherwise it would be the natural order). hence 5 (the value of two) goes before of 1 (the value of one which again is judge less then "two" as an object");

From this point on each value inserted in the queue with the for each will be compared with compare(Integer one, Integer two) with each element of the already formed queue, starting from the left to the right. in which the element just inserted and to be sorted is Integer two and the element already in the queue is Integer one.

Hope it helped.

[Henry Wong]

Nick Widelec wrote:
Just adding that oracle discourages the use of that technique "two-one" and they recommend to use "two.compareTo(one)" as if you inserted a negative value in your queue and, says, the Integer "two" has +3 as a value and the Integer "one" has -3 it will return 0 which the comparator sees it as meaning of equality, breaking also the "comparator consistent with "equals()" thing.

If "two" has a value of +3, and "one" has a value of -3, doesn't "two-one" return a value of +6? ... ie. Doesn't positive 3 minus negative 3 equals six?

Henry

[Nick Widelec]

Henry Wong wrote:

Nick Widelec wrote:
Just adding that oracle discourages the use of that technique "two-one" and they recommend to use "two.compareTo(one)" as if you inserted a negative value in your queue and, says, the Integer "two" has +3 as a value and the Integer "one" has -3 it will return 0 which the comparator sees it as meaning of equality, breaking also the "comparator consistent with "equals()" thing.

If "two" has a value of +3, and "one" has a value of -3, doesn't "two-one" return a value of +6? ... ie. Doesn't positive 3 minus negative 3 equals six?

Henry

Hi Henry,
You right, my bad, wrote it in a rush. I edited it now thanks for pointing it out.

[Chad Michaels]

Katherine Reut wrote:
So MY question is, the PQsort comparator works as Chad and Henry explained, but I am still unsure about where the comparator actually arranges the elements into the sorted order. Is it on line 13 and 14, when the queue is loaded? But then in the comparator, what are the values of the first and second parameters? Where do they come from? Is the first parameter (Integer one) the value of "x" in the for-each loop, and the second parameter (Integer two) the value of the last element added to pq2?

Hi Katherine,

Wow... this post brought back some memories. It's been a few years.

To give you a quick answer to your question: the comparator arranges the elements as they are inserted into the Queue. When a value is added from using offer(), the comparator's internal algorithm passes the existing values in the Queue as arguments to the compare() method and does this until the Queue is sorted. In fact, you can "see" this in action if you add some console statements. Change the code to reflect this:

	
   static class PQsort implements Comparator< Integer > { // inverse sort

      public int compare( Integer one , Integer two ) {

         System.out.println( "\tHere is argument one and two: " + one + " & " + two ) ; 
         return two - one ; // unboxing
      }
   }

And also...

for( int x : ia ) { 
   // load queue
   System.out.println( "I AM OFFERING : " + x ) ; 
   pq2.offer( x ) ;
}

So, if you run the above example with the console statements, you'll see when (and how) the items are inserted and sorted. The details of the sort algorithm (like how often it needs to traverse the Queue) used by the comparator is not something that interests me (though I'm guessing it's logarithmic). I'm sure you can search for it online or someone can explain it.

PS: I could be completely wrong with everything I've wrote.

[Henry Wong]

Nick Widelec wrote:
Hi Henry,
You right, my bad, wrote it in a rush. I edited it now thanks for pointing it out.

Nick, I am not sure of the point that you are trying to make -- as your edited response has a similar issue (just the sign has changed).

Nick Widelec wrote:
Just adding that oracle discourages the use of that technique "two-one" and they recommend to use "two.compareTo(one)" as if you inserted a negative value in your queue and, says, the Integer "two" has -3 as a value and the Integer "one" has +3 it will return 0 which the comparator sees it as meaning of equality, breaking also the "comparator consistent with "equals()" thing.
However the book shows it in that way, maybe to simplify and to concentrate in the "comparator" interface.

If "two" has a value of -3, and "one" has a value of +3, doesn't "two-one" return a value of -6? ... ie. Doesn't negative 3 minus positive 3 equals negative six?

Henry

[Katherine Reut]

Thank you, gentlemen, for helping me out with my question! And Chad, thanks for your good explanation, and for pointing out how to use the print statements in order to watch what is going on with Integer one and Integer two. That made it a lot more clear!

[Nick Widelec]

Henry Wong wrote:

Nick Widelec wrote:
Hi Henry,
You right, my bad, wrote it in a rush. I edited it now thanks for pointing it out.

Nick, I am not sure of the point that you are trying to make -- as your edited response has a similar issue (just the sign has changed).

Nick Widelec wrote:
Just adding that oracle discourages the use of that technique "two-one" and they recommend to use "two.compareTo(one)" as if you inserted a negative value in your queue and, says, the Integer "two" has -3 as a value and the Integer "one" has +3 it will return 0 which the comparator sees it as meaning of equality, breaking also the "comparator consistent with "equals()" thing.
However the book shows it in that way, maybe to simplify and to concentrate in the "comparator" interface.

If "two" has a value of -3, and "one" has a value of +3, doesn't "two-one" return a value of -6? ... ie. Doesn't negative 3 minus positive 3 equals negative six?

Henry

Hi Henry, you totally right my bad again.. bad day today.. mmmmm

I removed that bit which was not leading to anywhere. Thanks to reminding me that I seriously need to refresh some math.