Приоритетная очередь Java

Учебники
Java

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

Приоритетная очередь в Java

Класс java.util.PriorityQueue предоставляет нам реализацию такого типа данных, используя внутреннюю реализацию приоритетной кучи. Java PriorityQueue является неограниченной очередью. Она была введена в Java 1.5 и улучшена в релизе Java SE 8. PriorityQueue внутренне реализована с использованием структуры данных “приоритетная куча”. Вот иерархия классов PriorityQueue: Диаграмма классов PriorityQueue:

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

  1. PriorityQueue() – Создает PriorityQueue с размером по умолчанию, т.е. 11
  2. PriorityQueue(Collection c) – Создает PriorityQueue с элементами из указанной коллекции.
  3. PriorityQueue(int initialCapacity) – Создает PriorityQueue с указанной начальной емкостью
  4. PriorityQueue(int initialCapacity, Comparator comparator) – Создает PriorityQueue с указанной начальной емкостью и порядком элементов в соответствии с указанным компаратором
  5. PriorityQueue(PriorityQueue c) – Создает PriorityQueue, содержащий элементы из указанной очереди с приоритетом
  6. PriorityQueue(SortedSet c) – Создает PriorityQueue, содержащий элементы из указанного отсортированного набора

Элементы очереди с приоритетом упорядочены по их естественному порядку, если не предоставлен Comparator при создании. Элементы упорядочены по возрастанию по умолчанию, поэтому головой очереди является элемент с наименьшим приоритетом. Если есть два элемента, которые имеют право стать головой одновременно, эти связи разрешаются произвольно.

Пример Java PriorityQueue

Давайте создадим PriorityQueue, содержащую различные задачи:

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

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

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Методы PriorityQueue в Java

Теперь давайте рассмотрим все доступные методы для PriorityQueue и воспользуемся ими:

  1. Boolean add(E e) – Этот метод вставляет указанный элемент в очередь. Мы уже добавили 5 задач в нашу очередь с использованием этого метода.

  2. Comparator comparator() – Этот метод возвращает компаратор, используемый для упорядочения элементов в этой очереди. Он возвращает null, если компаратор не был указан, и очередь упорядочена в соответствии с естественным порядком ее элементов. Таким образом, если мы сделаем следующее:

    System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());

    Вывод будет следующим:

    null
java.util.Collections$ReverseComparator@15db9742

  3. boolean contains(Object o) – Возвращает true, если очередь содержит указанный элемент. Давайте проверим, принадлежит ли “task3” к очереди с приоритетами задач:

    System.out.println(tasks.contains("task3"));

    Это печатает:

    true

  4. boolean offer(E e) – Как и метод add(), этот метод также добавляет элемент в очередь. Методы offer() и add() фактически немного отличаются для очередей с ограниченной вместимостью, но в случае PriorityQueue они оба одинаковы. В отличие от add(), метод offer() не выбрасывает исключение, даже если не удается добавить элемент в очередь.

  5. E peek() – Извлекает голову этой очереди или возвращает null, если очередь пуста. Другими словами, он возвращает элемент с наивысшим приоритетом. Так что следующий код:

    System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());

    Дает нам:

    task1
task5

  6. E poll() – Этот метод также извлекает голову очереди (элемент с наивысшим приоритетом), или возвращает null, если очередь пуста. Но в отличие от peek(), он также удаляет элемент. Так что, если мы вызовем poll():

    System.out.println(“Poll on tasks: ”+tasks.poll());
System.out.println(“Poll on reverseTasks: ”+reverseTasks.poll());

    Затем peek:

    System.out.println(“Peek on tasks: ”+tasks.peek());
System.out.println(“Peek on reverseTasks: ”+reverseTasks.peek());

    У нас будет следующий вывод:

    Poll on tasks: task1
Poll on reverseTasks: task5
Peek on tasks: task2
Peek on reverseTasks: task4

  7. int size() – Возвращает количество элементов в очереди.

  8. boolean remove(Object o) – Удаляет указанный элемент из очереди, если он присутствует. Если два одинаковых элемента присутствуют, удаляется только один из них.

  9. Object[] toArray() – Возвращает массив, содержащий все элементы в очереди.

  10. T[] toArray(T[] a) – Возвращает массив, содержащий все элементы в очереди, и тип возвращаемого массива совпадает с указанным массивом.

  11. Iterator iterator() – Возвращает итератор для очереди.

  12. void clear() – Удаляет все элементы из очереди.

Помимо этого, PriorityQueue также наследует методы из классов Collection и Object.

Временная сложность Java PriorityQueue

  1. Для методов вставки и извлечения временная сложность составляет O(log(n))
  2. Для методов remove(Object) и contains(Object) временная сложность линейная
  3. Для методов извлечения временная сложность постоянная

Эта реализация приоритетной очереди не является потокобезопасной. Поэтому, если нам нужен синхронизированный доступ, мы должны использовать PriorityBlockingQueue. Ссылка: Документация по API

Source:
https://www.digitalocean.com/community/tutorials/priority-queue-java