Java PriorityQueue

PriorityQueue<E> — это куча в JDK. Это Queue, но вместо FIFO голова очереди всегда является наименьшим элементом согласно Comparator (или естественному порядку, если он не задан). Операция offer выполняется за O(log n), poll и peek от головы — за O(log n) и O(1) соответственно, а внутреннее хранилище — плоский массив без выделения узлов для каждого элемента. Это делает её подходящим инструментом для задач-планировщиков: «всегда обрабатывай то, что наиболее срочно».

Что здесь означает «голова»

В FIFO-очереди голова — тот, кто пришёл первым. В PriorityQueue голова — тот, у кого наименьшее значение в данный момент, а не наименьшее на момент вставки:

• peek() возвращает текущий наименьший элемент.
• poll() удаляет текущий наименьший элемент и восстанавливает кучу; следующий peek покажет новый наименьший.
• offer(x) вставляет и восстанавливает кучу; если x — новый наименьший, следующий peek вернёт его.

«Наименьший» определяется:

1. Comparator, переданным в конструктор, если он задан.
2. Иначе — естественным порядком элемента через Comparable. Если элементы не реализуют Comparable и Comparator не передан, первый вызов, требующий сравнения, бросит ClassCastException.

Режима максимальной кучи нет. Если нужна max-heap, передайте Comparator.reverseOrder() (или ваш компаратор в обратном порядке) — это стандартная идиома, используемая в примере ниже.

Создание очереди

// Natural order (Comparable elements).
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Reversed for max-heap behaviour.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom comparator — by length, then alphabetically.
PriorityQueue<String> byLen = new PriorityQueue<>(
    Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

// Pre-sized + comparator (initial capacity must come first).
PriorityQueue<String> bigByLen = new PriorityQueue<>(1_000,
    Comparator.comparingInt(String::length));

// From an existing collection.
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));

Конструктор с одним аргументом Collection работает за O(n) — он выполняет heapify оптом, а не n операций offer за O(log n) каждая. Полезно, когда все данные уже есть заранее.

Итерация НЕ идёт в порядке приоритета

Это неожиданность, с которой сталкивается большинство. Итерация по PriorityQueue обходит внутренний массив кучи в том порядке, в котором куча хранит свои узлы, — не в порядке возрастания:

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));
System.out.println(pq);                // possibly [10, 20, 30, 40]
for (int x : pq) System.out.print(x + " "); // possibly: 10 20 30 40
                                            // possibly: 10 40 30 20

Порядок вывода — деталь реализации расположения кучи. Чтобы получить элементы в порядке приоритета, нужно опустошить очередь:

while (!pq.isEmpty()) System.out.print(pq.poll() + " ");   // sorted

Имейте это в виду при использовании forEach, stream, toArray или простой печати очереди при отладке. Stream, возвращаемый stream(), не отсортирован, а добавление .sorted() требует, чтобы элементы реализовывали Comparable (или можно передать компаратор).

Изменение элемента после offer ломает кучу

Приоритет вычисляется в момент вставки. Если вы поместили элемент и затем изменили поле, по которому сравнивает компаратор, куча переходит в недопустимое состояние — poll может вернуть неверную голову, contains может не найти элемент, инвариант нарушен. Метода update или decrease-key не существует.

Два способа обойти это:

• Используйте неизменяемые элементы — записи с полями приоритета или записи-обёртки, например record Task(int priority, String name) {}. Тогда после вставки менять нечего.
• Удалите и вставьте снова, если нужно изменить приоритет: pq.remove(task) выполняется за O(n) (выполняет поиск), затем pq.offer(taskWithNewPriority) — за O(log n).

Для небольшой очереди удаление и повторная вставка — нормальный подход. Если вы реализуете алгоритм Дейкстры и нужна быстрая операция decrease-key, PriorityQueue не подходит — используйте индексированную кучу или TreeSet пар (priority, node).

null и потокобезопасность

Те же правила, что и для остальных Queue:

• Null не допускается. pq.offer(null) бросает NullPointerException.
• Не потокобезопасна. Для конкурентного доступа используйте PriorityBlockingQueue из пакета java.util.concurrent.

Практический пример: простой планировщик задач

Программа ниже использует PriorityQueue для планирования задач по приоритету (меньшее число = более срочная задача). Также показаны идиома max-heap и неожиданный порядок итерации.

Разбор вывода:

• toString() и forEach показали задачи в каком-то порядке — не отсортированном. Не используйте их для отладки «правильно ли расставлены приоритеты?» — опустошите очередь через poll, чтобы увидеть реальный порядок.
• Конструктор с коллекцией создал правильно упорядоченную кучу за один раз — это путь линейного heapify.
• Блок с мутацией в конце демонстрирует опасность в концентрированном виде. Мы изменили приоритет массива после того, как он был добавлен в очередь, куча не смогла перебалансироваться, и теперь peek возвращает неверный результат. Исправление — либо использовать неизменяемую обёртку, либо выполнить remove и offer после изменения.

Что дальше

Следующая глава посвящена реализации, к которой обращаются, когда нужна FIFO-очередь или стек или дек — и которую Javadoc JDK рекомендует по умолчанию для всех трёх: ArrayDeque. Именно этот класс выполняет большую часть работы за кулисами в примерах кода двух предыдущих глав.

Практика