How to iterate over a PriorityQueue?

Question

for (Event e : pq) 

doesn't iterate in the priority order.

while(!pq.isEmpty()){   Event e = pq.poll(); } 

This works but empties the queue.

Answer 1

From the Javadocs

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()).

There are probably other equivalent mechanisms.

Answer 2

You can't traverse a Priority Queue in that order because of the underlying implementation (I think it's min-heap in Java).

It's not a sorted array, so that you can just go from one element to the one with the lesser priority.

Peeking (read the top element heap in the heap) is constant time O(1) because it looks at the smallest element.

To get the second next one you must dequeue the smallest top element, that's how it works.
Dequeing (re-heapify = O(log n) time) isn't just a matter of taking that element out, the underlying structure rearranges itself in order to bring the element with the least priority first.

Also, to go through the entire priority queue to read all items in the sorted order, it is an O(n log(n)) operation.
So you may as well just grab all the elements in the queue and sort them (also O(n log (n)) )and then you can go through them as you wish. The only disadvantage is that you're holding an extra-copy of the queue.

Nonetheless, if you need to traverse the data in this way a priority queue may not be the right data structure for your needs.