PriorityQueue: примеры (JAVA)

Применение PriorityQueue в задачах с приоритетами
Раздел: Коллекции (Collection Framework) - Queue/Deque
PriorityQueue
типовые примерыPriorityQueue на javascript, c#, python, phpPriorityQueue изменения javaпримеры расширенные

Общее описание PriorityQueue

Класс java.util.PriorityQueue представляет собой реализацию приоритетной очереди на базе бинарной кучи (heap). Экземпляр хранит элементы так, что вызовы peek() и poll() возвращают элемент с наивысшим приоритетом согласно естественному порядку элементов (если тип реализует Comparable) или заданному Comparator. Класс не гарантирует стабильность при равных приоритетах и не является потокобезопасным.

Когда применяется

Применяется для задач, где требуется быстро извлекать элемент с минимальным/максимальным приоритетом: планировщики задач, алгоритмы маршрутизации (Dijkstra), топ-k выборки и т. п.

Конструкторы

  • PriorityQueue() - пустая очередь с начальной емкостью по умолчанию (обычно 11).
  • PriorityQueue(int initialCapacity) - очередь с указанной начальной емкостью; если передано значение <= 0, будет IllegalArgumentException.
  • PriorityQueue(Comparator comparator) - пустая очередь с заданным компаратором; comparator может быть null (будет использоваться Comparable элементов).
  • PriorityQueue(int initialCapacity, Comparator comparator) - сочетание вместимости и компаратора.
  • PriorityQueue(Collection c) - создаёт очередь и помещает элементы из коллекции; время построения O(n).
  • PriorityQueue(PriorityQueue c) и PriorityQueue(SortedSet c) - копирование из существующих структур.

Основные методы и их семантика

  • boolean add(E e) - добавляет элемент, возвращает true; при попытке добавить null бросает NullPointerException; в стандартной реализации всегда возвращает true, но контракт Collection допускает false при ограниченных реализациях.
  • boolean offer(E e) - эквивалент add(e) для очередей; возвращает true или бросает исключение при ошибке; используются в интерфейсе Queue.
  • E poll() - извлекает и возвращает элемент с максимальным приоритетом (минимальный по сравнению), или null, если очередь пуста.
  • E peek() - возвращает элемент с приоритетом, не удаляя, или null, если пуста.
  • E remove() - извлекает и возвращает элемент; если очередь пуста, бросает NoSuchElementException.
  • boolean remove(Object o) - удаляет один экземпляр равного элемента; сложность O(n).
  • E element() - аналог peek(), но если очередь пуста, бросает NoSuchElementException.
  • int size(), boolean isEmpty(), boolean contains(Object o), Iterator iterator() - стандартные операции коллекции. Итератор не гарантирует порядок извлечения и может бросить ConcurrentModificationException при структурных изменениях.
  • Comparator comparator() - возвращает компаратор или null, если используется естественный порядок.
  • Object[] toArray(), <T> T[] toArray(T[] a) - конвертация в массив; порядок не гарантирован как сортированный.
  • void clear() - очистка очереди.

Возвращаемые значения и исключения

  • add/offer: обычно true; add бросает NullPointerException при null.
  • peek/poll: возвращают null, если очередь пуста.
  • remove/element: бросают NoSuchElementException при пустой очереди.
  • Добавление несовместимых типов без компаратора вызывает ClassCastException при сравнении.

Производительность

  • add/offer/poll/remove(head) - O(log n).
  • remove(Object) и contains - O(n).
  • Построение из коллекции - O(n).

Короткие практические примеры

Пример 1. Простейшая очередь чисел (естественный порядок)

import java.util.PriorityQueue;

PriorityQueue pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);
System.out.println(pq.peek());
System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());
1
1
3
5
null

Пример 2. Обратный порядок через Comparator

import java.util.PriorityQueue;
import java.util.Comparator;

PriorityQueue pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.offer(2);
pq.offer(7);
pq.offer(4);
System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());
7
4
2

Пример 3. Очередь объектов с пользовательским компаратором

import java.util.PriorityQueue;

class Person {
  String name;
  int age;
  Person(String n, int a) { name = n; age = a; }
  public String toString() { return name + ":" + age; }
}

PriorityQueue pq = new PriorityQueue<>((a, b) -> Integer.compare(a.age, b.age));
pq.add(new Person("Anna", 30));
pq.add(new Person("Boris", 25));
System.out.println(pq.poll());
Boris:25

Пример 4. Поведение с null и смешанными типами

PriorityQueue pq = new PriorityQueue<>();
try {
  pq.add(null);
} catch (Exception e) {
  System.out.println(e.getClass().getSimpleName());
}

PriorityQueue mixed = new PriorityQueue<>();
mixed.add("a");
mixed.add(1); // на этапе сравнения может возникнуть ClassCastException


NullPointerException
ClassCastException (при попытке сравнить разные типы)
Похожие структуры в Java и их особенности


    
  
  • PriorityBlockingQueue
    • 
  
    Потокобезопасная неблокирующая приоритетная очередь для многопоточных сценариев; поддерживает блокирующие операции take(), put() нет (put == offer). Подходит, когда требуется конкурентный доступ без внешней синхронизации.
    

  
  • TreeSet / TreeMap
    • 
  
    Хранят элементы в отсортированном порядке и обеспечивают логарифмическую вставку/удаление. В отличие от PriorityQueue гарантируют упорядоченную итерацию. TreeSet запрещает дубликаты (по equals/compareTo).
    

  
  • ArrayDeque / LinkedList (как очередь)
    • 
  
    Подходят для FIFO-очередей, но не поддерживают приоритетную сортировку.
    

  
  • Collections.sort и списки
    • 
  
    Для редких извлечений максимума можно хранить список и сортировать по требованию; для частых извлечений это медленнее (O(n log n) на сортировку).
    

Аналоги в других языках и отличия


    
  
  • Python (heapq)
    • 
  
    Модуль heapq реализует мин-кучу на списке. Нет отдельного класса PriorityQueue с методами; операции push/pop - heapq.heappush/heapq.heappop. Пример:
    
  
    import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
print(heapq.heappop(h))
    
  
    1
    

  
  • JavaScript
    • 
  
    Встроенной структуры нет. Часто используется реализация бинарной кучи вручную или из npm (heap-js). Отличие: отсутствие стандартной, разные API.
    
  
    // простой минимальный heap (фрагмент)
class MinHeap { constructor(){ this.a=[] } push(x){ this.a.push(x); /* всплытие */ } pop(){ /* извлечь минимум */ } }

    
  
    (результат зависит от реализации)
    

  
  • PHP (SplPriorityQueue)
    • 
  
    Есть встроенная SplPriorityQueue с явной поддержкой приоритетов. Отличие: приоритет и данные передаются отдельно; поведение итератора специфично.
    
  
    $pq = new SplPriorityQueue();
$pq->insert('task1', 10);
$pq->insert('task2', 20);
echo $pq->extract();
    
  
    task2
    

  
  • C# (.NET 6+ PriorityQueue<TElement,TPriority>)
    • 
  
    В .NET 6 добавлен обобщённый PriorityQueue, где приоритет явно отделён от элемента; раньше использовались реализации на SortedSet или сторонние библиотеки.
    
  
    using System.Collections.Generic;
var pq = new PriorityQueue();
pq.Enqueue("a", 2);
pq.Enqueue("b", 1);
Console.WriteLine(pq.Dequeue());
    
  
    b
    

  
  • Go (container/heap)
    • 
  
    Пакет container/heap предоставляет интерфейс для реализации кучи над срезом. Требуется реализовать ряд методов для структуры. Отличие: низкоуровневая кастомизация через интерфейс.
    
  
    // пример опущен в целях краткости, API: heap.Init, heap.Push, heap.Pop
    
  
    (типовой результат зависит от реализации)
    

  
  • Kotlin
    • 
  
    Используется java.util.PriorityQueue напрямую; синтаксис удобнее, но семантика совпадает.
    

  
  • Lua
    • 
  
    Стандартной структуры нет; реализуется на таблицах / функциях для heap. Отличие - ручная реализация и отсутствие строгой типизации.
    

  
  • SQL
    • 
  
    Приоритетная выборка достигается ORDER BY с LIMIT; отличается тем, что данные извлекаются из БД и упорядочиваются сервером.
    

Типичные ошибки и их проявления


    
  
  • Добавление null
    • 
  
    PriorityQueue не допускает null. Пример:
    
  
    PriorityQueue pq = new PriorityQueue<>();
pq.add(null);
    
  
    NullPointerException
    

  
  • Смешивание несравнимых типов
    • 
  
    Добавление объектов разных классов без общего Comparator приводит к ClassCastException при попытке сравнения элементов:
    
  
    PriorityQueue pq = new PriorityQueue();
pq.add("s");
pq.add(10);
pq.poll(); // может вызвать ClassCastException
    
  
    ClassCastException
    

  
  • Использование element()/remove() для пустой очереди
    • 
  
    element() и remove() бросают NoSuchElementException, тогда как peek() и poll() возвращают null.
    
  
    PriorityQueue pq = new PriorityQueue<>();
pq.element();
    
  
    NoSuchElementException
    

  
  • ConcurrentModificationException при итерации
    • 
  
    При структурных изменениях коллекции во время обхода итератор может бросить ConcurrentModificationException.
    

  
  • Ожидание упорядоченного итератора
    • 
  
    Итератор не возвращает элементы в приоритетном порядке. Для получения упорядоченного списка следует извлекать элементы через poll или скопировать в массив и отсортировать.
    

  
  • Ожидаемая стабильность
    • 
  
    PriorityQueue не обеспечивает стабильность при равных ключах; для сохранения исходного порядка требуется добавлять дополнительный tie-breaker в компаратор.
    

Изменения и история


Класс PriorityQueue присутствует в Java с версии 1.5 (включая обобщения). В последующих релизах изменений API было немного: улучшения производительности и интеграция с общими возможностями коллекций (например, методы по умолчанию интерфейсов Collection из Java 8, поддержка Stream API на уровне коллекций). Специальных крупных изменений API в последних версиях не вводилось - основная модель и методы остались прежними. Для многопоточных сценариев рекомендуется использовать PriorityBlockingQueue или внешнюю синхронизацию.
Расширенные и редкие сценарии использования


Пример A. Top-K - удержание K наибольших элементов (минимальная кучи размера K)


Пример java
import java.util.PriorityQueue;

int K = 3;
PriorityQueue topK = new PriorityQueue<>();
int[] stream = {5, 1, 9, 3, 7, 6};
for (int v : stream) {
  if (topK.size() < K) topK.add(v);
  else if (v > topK.peek()) {
    topK.poll();
    topK.add(v);
  }
}
while (!topK.isEmpty()) System.out.println(topK.poll());


5
7
9
(в порядке возрастания, чтобы получить убывающий список, собрать в список и отсортировать)



Пример B. Слияние k отсортированных списков


Пример java
import java.util.*;

class Node { int val; int listIdx; int pos; Node(int v,int i,int p){val=v;listIdx=i;pos=p;} }

List> lists = Arrays.asList(
  Arrays.asList(1,4,7),
  Arrays.asList(2,5,8),
  Arrays.asList(3,6,9)
);
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
for (int i=0;i<lists.size();i++) if (!lists.get(i).isEmpty()) pq.add(new Node(lists.get(i).get(0), i, 0));
List result = new ArrayList<>();
while (!pq.isEmpty()) {
  Node n = pq.poll();
  result.add(n.val);
  int nextPos = n.pos + 1;
  if (nextPos < lists.get(n.listIdx).size()) {
    pq.add(new Node(lists.get(n.listIdx).get(nextPos), n.listIdx, nextPos));
  }
}
System.out.println(result);


[1, 2, 3, 4, 5, 6, 7, 8, 9]



Пример C. Dijkstra (упрощённый фрагмент)


Пример java
import java.util.*;

class Edge { int to; int w; Edge(int t,int ww){to=t;w=ww;} }
class State { int v; int dist; State(int v,int d){this.v=v;this.dist=d;} }

// comparator по расстоянию
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(s -> s.dist));
// старт
pq.add(new State(0, 0));
// далее извлечение и обновление расстояний



(типичный результат: минимальные расстояния до вершин)



Пример D. Ограниченная по размеру очередь с пользовательским компаратором и tie-breaker


Пример java
import java.util.*;

class Item { String id; int priority; long seq; Item(String i,int p,long s){id=i;priority=p;seq=s;} }

// компаратор: по приоритету, при равенстве - по seq (меньше seq выше в приоритете)
PriorityQueue pq = new PriorityQueue<>((a,b) -> {
  int c = Integer.compare(a.priority, b.priority);
  return c != 0 ? c : Long.compare(a.seq, b.seq);
});

// удержание сверху N элементов
int N = 5;
long seq = 0;
for (int i=0;i<10;i++) {
  pq.add(new Item("it"+i, i%3, seq++));
  if (pq.size() > N) pq.poll();
}
while(!pq.isEmpty()) System.out.println(pq.poll().id + " " + pq.poll()); // демонстрация



(вывод демонстрирует отбор по приоритету с детерминированным tie-break)



Пример E. Конкурентная схема с PriorityBlockingQueue


Пример java
import java.util.concurrent.PriorityBlockingQueue;

PriorityBlockingQueue queue = new PriorityBlockingQueue<>(11, (a,b) -> 0); // пример компаратора
// потребители могут вызывать take(), производители - put()/offer()



(в многопоточной среде очереди блокируют при извлечении пустой очереди)



Примечания


При разработке алгоритмов с PriorityQueue стоит учитывать, что итерация не отсортирована и что для детерминированного поведения при равных ключах требуется tie-breaker. Для многопоточных вариантов - выбирать специализированные реализации.
	



	
джава PriorityQueue function comments
En
PriorityQueue An unbounded priority queue based on a priority heap