Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

PriorityQueue  RSS feed

Siva Masilamani
Ranch Hand
Posts: 385
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

I have a doubt about the priority Queue in JDK 1.6

I know it keeps the element in order either in natural order or by comparator

But when i use the for each loop i can not under stand the output it produces .Please see the code below

if i run the above code the output is


As you can see none of the output is in natural order.However if use TreeSet then, for each displays the output in natural order.

Also if use pool,peek or remove the ouput depends on the natural order and i can get the correct output i.e. if i use poll() in Integer Queue the output is 0 for the first time and 1 for the second time.

Then why does it fail to display the element in order when for each loop is used?

[NK: Added code tags. Please UseCodeTags while posting code]
Mike Simmons
Ranch Hand
Posts: 3090
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Take a look at the PriorityQueue API:
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

The reason for this is that a PriorityQueue is optimized for fast insertion and retrieval of elements, but not for iteration. It knows how to organize its data internally so that every time you call poll() or peek(), it will get the correct highest-priority element. But in order to iterate the entire tree (without actually removing anything from the queue), going in order would require additional work that would slow down the other operations. They chose instead to give you a fast iterator that isn't necessarily correct in order, rather than a slower iterator that iterates in order. So if you care about the order, don't use the iterator.
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!