Класс PriorityQueue в Java - Вопросы

PriorityQueue хранит элементы в массиве Object[], организованном как бинарная куча: каждый элемент не больше своих потомков. Для элемента с индексом i потомки лежат в ячейках 2*i + 1 и 2*i + 2, родитель — в (i - 1) / 2, поэтому наименьший элемент всегда в ячейке 0 — это голова очереди. Такая куча называется min-heap; с компаратором обратного порядка вверху оказывается наибольший элемент — max-heap.

При offer() новый элемент записывается в конец массива и всплывает (sift up), меняясь с родителем, пока тот больше. При poll() на место головы ставится последний элемент и погружается (sift down). Обе операции проходят не больше одного пути от корня до листа — O(log n). Между «соседями» порядка нет: после offer(5, 1, 4, 2, 3) массив выглядит как [1, 2, 4, 5, 3].

• offer()/add(), poll()/remove() — O(log n): элемент всплывает или погружается по одному пути кучи.
• peek()/element(), size(), isEmpty() — O(1): голова всегда в ячейке 0.
• contains(Object) и remove(Object) — O(n): куча не упорядочена для поиска, массив перебирается целиком. remove(Object) сравнивает через equals(), а не через компаратор.
• addAll(c) добавляет по одному элементу — O(m log n); конструктор PriorityQueue(c) строит кучу сразу за O(n).

По той же причине в min-heap минимум доступен за O(1), а максимум ищется за O(n): он может лежать в любом листе, а листьев около n/2. Если нужны оба конца, держат две кучи или берут TreeSet.

Итератор, for-each, toString() и toArray() обходят внутренний массив кучи, поэтому порядок не совпадает с порядком приоритета: после offer(5, 1, 4, 2, 3) for-each выводит 1 2 4 5 3. Гарантирован только первый элемент — голова.

Отсортированный порядок дают два способа:

• последовательные вызовы poll() — порядок правильный, но очередь опустошается;
• сортировка копии: pq.stream().sorted().toList() (очередь не меняется). Для очереди с компаратором — pq.stream().sorted(pq.comparator()); при естественном порядке comparator() возвращает null, и sorted(null) бросит NullPointerException, поэтому там нужен просто sorted().

Класс элементов должен реализовать Comparable, или в конструктор передают Comparator:

PriorityQueue<Task> tasks =
        new PriorityQueue<>(Comparator.comparingInt(Task::priority));

Иначе код скомпилируется, но offer() бросит ClassCastException (в JDK 11+ — уже на первом элементе). Массивы int[] тоже не Comparable: new PriorityQueue<int[]>((a, b) -> Integer.compare(a[1], b[1])).

Max-heap — компаратор обратного порядка: new PriorityQueue<>(Collections.reverseOrder()) или Comparator.comparingInt(Task::priority).reversed(). Запись (a, b) -> b - a лучше не использовать: вычитание переполняется на больших числах, безопасно — (a, b) -> Integer.compare(b, a).

Порядок элементов с равным приоритетом не гарантирован: куча нестабильна. Если нужен FIFO среди равных, добавляют порядковый номер вторым критерием: .thenComparingLong(Task::seq).

Изменение приоритета. Куча перестраивается только при offer() и poll(), поэтому изменение поля, по которому сравниваются объекты, она не замечает — порядок извлечения становится неверным. Метода «обновить приоритет» нет: объект удаляют (remove(obj), O(n)), меняют поле и добавляют заново. Надёжнее делать поля сравнения неизменяемыми, например через record.

Размер. Число в конструкторе — только начальная ёмкость (по умолчанию 11, меньше 1 — IllegalArgumentException), массив растёт сам, offer() всегда возвращает true. Ограничение пишут вручную: после offer() проверяют size() и вызывают poll() — так ищут k наибольших элементов за O(n log k).

Потоки. PriorityQueue не синхронизирована, одновременные offer() и poll() могут повредить кучу. Потокобезопасный аналог — java.util.concurrent.PriorityBlockingQueue с блокирующим take().

Обе коллекции упорядочивают элементы через Comparable или Comparator, но устроены по-разному:

• Устройство: PriorityQueue — бинарная куча на одном массиве; TreeSet — красно-чёрное дерево (внутри TreeMap) с узлом на каждый элемент.
• Дубликаты: PriorityQueue их хранит; TreeSet не добавит элемент, для которого компаратор вернул 0.
• Доступ: у PriorityQueue только голова (peek() за O(1)); у TreeSet оба конца и соседи (first(), last(), ceiling(), floor()) за O(log n).
• Обход: итератор PriorityQueue не сортирует, у TreeSet обход отсортирован.
• Поиск и удаление элемента: O(n) против O(log n).

PriorityQueue выбирают для обработки по приоритету, планировщиков, top-k и алгоритмов на графах; TreeSet — для уникальных отсортированных значений, диапазонов и случаев, когда нужны и минимум, и максимум.