Iterating over a PriorityQueue is NOT ordered

I stumbled across a little Java gotcha recently when trying to order a collection of Java objects.  For some reason I decided to use a PriorityQueue because I wanted to maintain duplicates, so TreeSet and TreeMap were ruled out.

Unfortunately, the PriorityQueue is only ordered when remove/peek/poll-ing objects from the collection. NOT when iterating over the collection. This fun fact is clearly identified in the PriorityQueue JavaDocs:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

Unfortunately the JavaDocs aren’t very obvious even if you do happen to specifically access the iterator (and really isn’t obvious from a for-loop perspective).

While it makes perfect sense in retrospect (due to the internals of the underlying heap), it was only by chance that I caught my mistake and made the fix:

final PriorityQueue<MyObject> ordered = ...;
while (ordered.size() > 0) {
   final MyObject next = ordered.remove();
   ...
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>