my dog learned polymorphism*
The moose likes Beginning Java and the fly likes Doubt in priority Queue implementation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Doubt in priority Queue implementation" Watch "Doubt in priority Queue implementation" New topic
Author

Doubt in priority Queue implementation

vijay makam
Ranch Hand

Joined: Sep 06, 2008
Posts: 31
As far as my understanding goes after reading some java books I think If we are not using a comparator for our priority queue then the insertion will FIFO. But after executing the below program I am getting a different one.



Please let me know what is happening in the above piece of code.

Thanks in advance
[edit]Alter spacing to avoid smilies, and add code tags. CR[/edit]
[ September 30, 2008: Message edited by: Campbell Ritchie ]

Regards,
vijay
Piet Verdriet
Ranch Hand

Joined: Feb 25, 2006
Posts: 266
Originally posted by vijay makam:
As far as my understanding goes after reading some java books I think If we are not using a comparator for our priority queue then the insertion will FIFO. ...


No, that is not correct. If no Comparator is provided, the elements get sorted according their natural order. Strings are compared lexicographically. So "B" comes after "A" but "B" comes before "C": adding "C", "A" and "B" will result in the PQ=["A","B","C"].

HTH
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18764
    
  40

And here is the relevant paragraph in the JavaDoc...

This queue orders elements according to an order specified at construction time, which is specified either according to their natural order (see Comparable), or according to a Comparator, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).


Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
vijay makam
Ranch Hand

Joined: Sep 06, 2008
Posts: 31
Hi Piet,

Thanks for your reply. But that doesn't solve my confusion.
The output I am getting is neither in the insertion order nor in the natural order.
Here's a snapshot of the partial output (after the first for-each loop).
pq's element: apple
pq's element: orange
pq's element: banana
pq's element: peach
pq's element: plum
Piet Verdriet
Ranch Hand

Joined: Feb 25, 2006
Posts: 266
Hi, run this code to see how PQ internally orders it's elements (and when!):



To quote the API doc for PQ:

"The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray())"


http://java.sun.com/j2se/1.5.0/docs/api/java/util/PriorityQueue.html
[ October 01, 2008: Message edited by: Piet Verdriet ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Doubt in priority Queue implementation