Краткий ответ

Итератор PriorityQueue не обязан выдавать элементы по возрастанию приоритета, потому что очередь хранит не полностью отсортированную последовательность, а кучу. Куча гарантирует доступ к минимальному или максимальному элементу через peek() и его извлечение через poll(), но не задаёт сортированный порядок обхода всех элементов.

Если требуется получить элементы по приоритету, их нужно последовательно извлекать через poll() либо скопировать коллекцию и отдельно отсортировать. Порядок, возвращаемый iterator(), не следует использовать как часть логики приложения.

Исторический контекст

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

Бинарная куча решает эту проблему компромиссом: она поддерживает частичный порядок, достаточный для быстрого доступа к корневому элементу. Благодаря этому добавление и извлечение обычно требуют O(log n), а просмотр следующего элемента — O(1).

Постановка проблемы

Разработчик может увидеть несколько элементов в PriorityQueue и предположить, что обход через for-each или iterator() даст их в порядке приоритета. Это предположение ошибочно: внутренний массив кучи не является отсортированным массивом.

Если использовать такой обход для отправки задач, выбора ближайшего события или формирования отсортированного отчёта, программа может обработать элементы в неверной последовательности. При этом вызовы peek() и poll() будут соблюдать контракт очереди, поэтому ошибка может проявляться только в конкретном способе обхода.

Подробное решение

Внутри PriorityQueue обычно поддерживается бинарная куча, представленная массивом. Для минимальной кучи значение родителя не больше значений его потомков, но элементы на соседних ветвях между собой не обязаны быть упорядочены.

Поэтому корневой элемент имеет наивысший приоритет, однако второй элемент массива не обязан быть вторым по приоритету во всей очереди. Итератор проходит внутреннее представление, а не выполняет последовательное извлечение корня с восстановлением свойства кучи.

Минимальный пример:

import java.util.PriorityQueue;

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(5);
queue.add(1);
queue.add(3);

for (Integer value : queue) {
    System.out.println(value); // порядок не гарантирован как 1, 3, 5
}

while (!queue.isEmpty()) {
    System.out.println(queue.poll()); // 1, затем 3, затем 5
}

Вызов poll() удаляет корень кучи, после чего реализация восстанавливает инвариант за O(log n). Последовательность таких вызовов даёт порядок приоритета; один проход итератором такого результата не гарантирует.

Операция peek() имеет ожидаемую сложность O(1), offer() и poll() — O(log n), а обход — O(n), но без сортированного порядка. Для одинаковых приоритетов стабильный порядок обычно не гарантируется, поэтому нельзя рассчитывать, что элементы с равными ключами выйдут в порядке добавления.

Если нужна полностью отсортированная структура с постоянным поддержанием порядка, можно рассмотреть TreeSet или другую сортируемую коллекцию, но это меняет семантику: например, TreeSet не хранит дубликаты согласно своему сравнению. Если нужна очередь для многопоточного доступа, обычная PriorityQueue не подходит без внешней синхронизации; следует рассматривать потокобезопасную альтернативу, например PriorityBlockingQueue, с учётом её собственной семантики.

Ситуация из практики

В сервисе планирования фоновых задач нужно всегда запускать задачу с ближайшим сроком выполнения. Один из вариантов — хранить задачи в ArrayList и перед каждым запуском сортировать список. Он прост, но регулярная сортировка создаёт лишние затраты и усложняет обработку частых добавлений.

Второй вариант — использовать TreeSet. Он поддерживает порядок и быстрый доступ к первому элементу, но требует корректного сравнения и может считать две разные задачи одинаковыми, если компаратор возвращает ноль. Это опасно, если задачи имеют одинаковый срок, но должны храниться обе.

Выбран PriorityQueue: новые задачи добавляются за ожидаемое O(log n), ближайшая задача извлекается через poll() также за ожидаемое O(log n), а peek() позволяет посмотреть следующую задачу за O(1). При этом отчёт о задачах формируется отдельной копией с сортировкой, потому что итератор очереди не предназначен для получения упорядоченного представления.

Что кандидаты часто упускают

1. Дополнительный вопрос: можно ли использовать PriorityQueue для получения отсортированного списка без изменения исходной очереди?

Нельзя полагаться на её итератор: он не обязан возвращать элементы по приоритету. Практический вариант — создать копию очереди и последовательно вызывать poll() у копии; исходная очередь при этом останется неизменной, а стоимость извлечения всех элементов составит ожидаемо O(n log n).

Другой вариант — скопировать элементы в список и отсортировать его. Он также не изменяет очередь, а итоговая сложность обычно составляет O(n log n). Выбор зависит от требований к памяти, наличия уже готовой коллекции и необходимости сохранить исходную структуру.

2. Дополнительный вопрос: гарантирует ли PriorityQueue порядок добавления для элементов с одинаковым приоритетом?

Нет, стабильность не гарантируется. Когда компаратор или естественный порядок считают два элемента равными по приоритету, структура обязана поддерживать их приоритетное равенство, но не обязана сохранять FIFO-порядок между ними.

Если стабильность важна, в элемент обычно добавляют уникальный порядковый номер и сравнивают сначала приоритет, затем этот номер. Такой подход превращает равные приоритеты в однозначный порядок, но увеличивает размер состояния элемента и требует корректно поддерживать счётчик.

3. Дополнительный вопрос: почему нельзя считать внутренний порядок PriorityQueue отсортированным даже после добавления элементов в отсортированной последовательности?

Потому что вставка поддерживает только инвариант кучи: новый элемент перемещается вверх, пока не займёт допустимое место относительно родителей. Куча не выполняет перестановку всех элементов в глобально отсортированный порядок.

Даже если элементы поступали отсортированными, дальнейшие удаления и добавления меняют форму кучи, а внутренние позиции отражают структуру дерева, а не полный порядок значений. Гарантированный приоритетный порядок получается только через операции доступа к корню — peek() или poll().