Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Priority Queue Ordering Question

 
Joshua Smith
Ranch Hand
Posts: 193
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic