This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.
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 Alter spacing to avoid smilies, and add code tags. CR[/edit] [ September 30, 2008: Message edited by: Campbell Ritchie ]
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"].
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).
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
Joined: Feb 25, 2006
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())"