How Priority Queue in Java is Working

Source Code

1. import java.util.*;  
2. class PQ{  
3.     static class PQsort implements Comparator<Integer>{   // inverse sort  
4.         public int compare(Integer one, Integer two){  
5.             return two - one;           // unboxing  
6.         }  
7.     }  
8.     public static void main(String[] args){  
9.         int[] ia = {1,5,3,7,6,9,8};         // unordered data  
10.         PriorityQueue<Integer> pq1 =   
11.             new PriorityQueue<Integer>();     // use natural order  
12.           
13.         for (int x : ia)                // load queue  
14.             pq1.offer(x);  
15.               
16.         for (int x : ia)                // review queue  
17.             System.out.print(pq1.poll() + " ");  
18.         System.out.println("");  
19.               
20.         PQsort pqs = new PQsort();          // get a Comparator  
21.         PriorityQueue<Integer> pq2 =   
22.             new PriorityQueue<Integer>(10,pqs);   // use Comparator  
23.               
24.         for (int x : ia)                // load queue  
25.             pq2.offer(x);  
26.           
27.           
28.         for (int x : ia)                // review queue  
29.             System.out.print(pq2.poll() + " ");  
30.           
31.         System.out.println(" ");  
32.     }  
33. } 

 Explanation

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. 

source