• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Doubt in priority Queue implementation

 
vijay makam
Ranch Hand
Posts: 31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Piet Verdriet
Ranch Hand
Posts: 266
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 21024
78
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
vijay makam
Ranch Hand
Posts: 31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 266
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic