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

PriorityQueues are implemented using binary heap. A heap is not a sorted structure and it is partially ordered. Each element has a “priority” associated with it. Using a heap to implement a priority queue, it will always have the element of highest priority in the root node of the heap. so in a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue. Heap is updated after each removal of elements to maintain the heap property