The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue. (...) 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()).
The toString method of PQ uses the iterator, I guess. The fact that PriorityQueue is ordered, but the iterator has no order frequently results in some confusion... Can we call this a bug?