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

Это прямо из Java Docs:

Этот класс и его итератор реализуют все необязательные методы интерфейсов Collection и Iterator. Итератор, предоставленный в методе iterator(), не гарантирует обход элементов приоритетной очереди в каком-либо определенном порядке. Если вам нужен упорядоченный обход, рассмотрите возможность использования Arrays.sort(pq.toArray()).

Итак, в принципе, мой PriorityQueue работает нормально, но вывод его на экран с использованием собственного встроенного метода toString () заставил меня увидеть эту аномалию в действии, и мне было интересно, может ли кто-нибудь объяснить, почему предоставленный (и используемый внутренне) итератор не проходит PriorityQueue в его естественном порядке?

Потому что базовая структура данных это не поддерживает. Двоичная куча упорядочена только частично, с наименьшим элементом в корне. Когда вы удаляете это, куча переупорядочивается таким образом, что следующий наименьший элемент находится в корне. Эффективного алгоритма упорядоченного обхода не существует, поэтому в Java его нет.

Приоритетные очереди реализованы с использованием двоичной кучи. Куча - это не отсортированная структура, и она частично упорядочена. С каждым элементом связан “приоритет”. Используя кучу для реализации приоритетной очереди, в корневом узле кучи всегда будет элемент с наивысшим приоритетом. таким образом, в приоритетной очереди элемент с высоким приоритетом обслуживается перед элементом с низким приоритетом. Если два элемента имеют одинаковый приоритет, они обслуживаются в соответствии с их порядком в очереди. Куча обновляется после каждого удаления элементов для сохранения свойства heap

На первый взгляд, он, вероятно, обходит данные в том порядке, в котором они хранятся. Чтобы минимизировать время вставки элемента в очередь, он обычно не хранит все элементы в отсортированном порядке.

Ну, как говорит Javadoc, именно так это и было реализовано. Очередь приоритетов, вероятно, использует двоичную кучу в качестве базовой структуры данных. При удалении элементов порядок в куче переупорядочивается, чтобы сохранить свойство heap .

Во-вторых, неразумно привязывать конкретную реализацию (навязывать порядок сортировки). С текущей реализацией вы можете просматривать ее в любом порядке и использовать любую реализацию.