Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Priority Queue Ordering Question

Joshua Smith
Ranch Hand
Posts: 193
What's the output?

Since a PriorityQueue is ordered by the natural order (alphabetical in this case) by default and the head of the queue is "the least element with respect to the specified ordering" (PriorityQueue API), I would have guessed this:

[aaa, bbb, ccc, ddd, eee]
aaa
[aaa, bbb, ccc, ddd, eee]
aaa
[bbb, ccc, ddd, eee]
bbb
[ccc, ddd, eee]

When I run it under Java 5 I get this:

[aaa, bbb, ccc, ddd, eee]
aaa
[aaa, bbb, ccc, ddd, eee]
aaa
[ bbb, ddd, ccc, eee ]
bbb
[ccc, ddd, eee]

Why [bbb, ddd, ccc, eee] instead of [bbb, ccc, ddd, eee]? Can anyone tell me why line A behaves the way it does?

Is it simply a matter of the elements not being sorted in the collection itself (and as such, not showing up ordered in the toString()), but only being ordered when it comes to the methods that operate on it (peek, poll, etc)?

Thanks,
Josh

Barry Gaunt
Ranch Hand
Posts: 7729
Notice this part of the API description:
This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. 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()).

I guess that toString (inherited from AbstractCollection) only calls the iterator of PriorityQueue.

Joshua Smith
Ranch Hand
Posts: 193
Thank you Barry. That was my suspicion.

Since queues are all about ordering (FIFO, LIFO, who comes next etc) I just had this unfounded suspicion that toString() and even the Iterator would pay attention to that stuff. Judging by what you quoted in the API, that doesn't seem to be the case.

Thanks,
Josh