The built-in iterator for java's PriorityQueue does not traverse the data structure in any particular order. Why?

Question

This is straight from the Java Docs:

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 priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

So basically, my PriorityQueue works fine, but printing it out to the screen using its own built in toString() method caused me to see this anomaly in action, and was wondering if someone could explain why it is that the iterator provided (and used internally) does not traverse the PriorityQueue in its natural order?

Answer 1

Because the underlying data structure doesn't support it. A binary heap is only partially ordered, with the smallest element at the root. When you remove that, the heap is reordered so that the next smallest element is at the root. There is no efficient ordered traversal algorithm so none is provided in Java.

Answer 2

At first guess, it's probably traversing the data in the order in which it's stored. To minimize the time to insert an item in the queue, it doesn't normally store all the items in sorted order.

Answer 3

Well, as the Javadoc says, that's how it's been implemented. The priority queue probably uses a binary heap as the underlying data structure. When you remove items, the heap is reordered to preserve the heap property.

Secondly, it's unwise to tie in a specific implementation (forcing a sorted order). With the current implementation, you are free to traverse it in any order and use any implementation.

Answer 4

Binary heaps are an efficient way of implementing priority queues. The only guarantee about order that a heap makes is that the item at the top has the highest priority (maybe it is the "biggest" or "smallest" according to some order). A heap is a binary tree that has the properties: Shape property: the tree fills up from top to bottom left to right Order prperty: the element at any node is bigger (or smaller if smallest has highest priority) than its two children nodes. When the iterator visits all the elements it probably does so in a level-order traversal, i.e. it visits each node in each level in turn before going on to the next level. Since the only guarantee about order that is made that a node has a higher priority than its children, the nodes in each level will be in no particular order.