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

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

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

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

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

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

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

Неверная оценка может привести к проблемам в планировщике задач или алгоритме поиска: замена PriorityQueue на структуру с линейным поиском минимума изменит суммарную сложность обработки большого числа элементов.

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

В куче для каждого узла выполняется условие: его приоритет не больше приоритетов потомков. Поэтому корень всегда содержит минимальный элемент, а его позиция в массиве известна заранее. Чтение корня не требует обхода структуры и занимает O(1).

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

import java.util.PriorityQueue;

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(7); // O(log n)
queue.add(2); // O(log n)
queue.add(5); // O(log n)

int head = queue.peek(); // O(1)
int removed = queue.poll(); // O(log n)

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

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

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

В сервисе обработки заданий нужно постоянно выбирать задачу с наименьшим сроком выполнения. Вариант с ArrayList потребовал бы поиска минимума за O(n) при каждом извлечении. Это даёт квадратичную сложность при последовательной обработке большого числа задач.

TreeSet обеспечивает упорядоченность и операции порядка O(log n), но не допускает несколько элементов, которые компаратор считает эквивалентными. Кроме того, он хранит полноценное сбалансированное дерево, что может иметь большие накладные расходы.

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

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

Означает ли peek() сортировку всей очереди?

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

Какова сложность создания PriorityQueue из набора элементов?

Если элементы помещаются в очередь по одному, суммарная сложность обычно составляет O(n log n). При построении кучи из уже имеющегося массива методом bottom-up heapify можно получить O(n), поскольку просеивание выполняется начиная с внутренних узлов, и большинство узлов находится на небольшой глубине.

Можно ли использовать PriorityQueue для поиска произвольного элемента за логарифмическое время?

Нет. Куча эффективно сообщает только о корневом элементе. Для contains или remove(Object) требуется проверить позиции массива, и в общем случае это занимает O(n). Если нужны быстрые произвольные поиски и упорядоченный обход, следует рассмотреть другую структуру, например TreeSet или дополнительный индекс.