File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Priority Queue

 
Srividhya Kiran
Ranch Hand
Posts: 166
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
import java.util.*;

class PQ
{
static class PQSort implements Comparator<Integer>
{
public int compare(Integer one,Integer two)
{
return two-one;
}
}

public static void main(String args[])
{
int[] ia={1,5,3,7,6,9,8};
PriorityQueue<Integer> pq1=new PriorityQueue<Integer>();

for(int x:ia)
pq1.offer(x);
for(int x:ia)
System.out.print(pq1.poll()+ " ");
System.out.println("");

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

System.out.println("Size:"+pq2.size());
System.out.println("peek:"+pq2.peek());
System.out.println("size:"+pq2.size());
System.out.println("poll:"+pq2.poll());
System.out.println("size:"+pq2.size());

for(int x:ia)
System.out.println(pq2.poll()+"");
}
}

Can someone expalin to me this code. It is given in K&B pg no: 567. But I am not able to understand the explanation given there.
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to JavaRanch!

I think we would be able to help you better if you told us exactly what you are questioning about this code. Otherwise, we might spend a lot of time explaining details you already know, and maybe even missing the details you need help with.
 
Srividhya Kiran
Ranch Hand
Posts: 166
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello marc

I am not able to follow how the compare method works. And how the values are compared and loaded in the queue. K&B says we follow opposite of the natural ordering. But I don see the output that way.

Thanks
Srividhya
 
Sheryl Pinto
Greenhorn
Posts: 6
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Srividhya,

pq2 doesnt have any elements and the output wont make any sense unless you add elements.
Insert the below snippet after the line

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



Then you will be able to see the reverse sort results.

Sheryl.
 
Srividhya Kiran
Ranch Hand
Posts: 166
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Sheryl

Thanks for your reply. But I wanted to know how the two elements are actually compared internally in the compare

Srividhya
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The compare(o1, o2) method returns an int indicating how o1 and o2 compare to each other. If o1 should come before o2, then a negative int is returned. If o1 should come after o2, then a positive int is returned. If o1 and o2 are "equal," then zero is returned.

In this example, the compare method returns the difference of (o2 - o1).

So if o1 is greater than o2, then a negative int is returned, indicating that o1 should come before o2. On the other hand, if o1 is less than o2, then a positive int is returned, indicating that o1 should come after o2.

Because the method subtracts o1 from o2 (instead of the other way around), it gives the opposite of natural ordering, because it puts larger values before smaller values.
 
Siri Naray
Ranch Hand
Posts: 105
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That explains the logic how they are compared, but what is that 10 in
PriorityQueue<Integer> pq2=new PriorityQueue<Integer>(10,pqs);???

Sirisha
 
sharad sinha
Greenhorn
Posts: 26
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
10 is the initial Capacity of the PriorityQueue. Things like this can be easily clarified by looking at the api docs click
Also you have missed an important part in the question, marked load queue

HTH.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic