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!