Класс PriorityQueue<E>

Type Parameters:
E - тип элементов, хранящихся в этой очереди
Все реализованные интерфейсы:
Serializable, Iterable<E>, Collection<E>, Queue<E> 
public class PriorityQueue<E>
extends AbstractQueue<E>
implements Serializable

Безграничная очередь с приоритетами очередь, основанная на куче приоритетов. Элементы очереди с приоритетами упорядочены в соответствии с их естественным порядком или с помощью Comparator, предоставленного во время создания очереди, в зависимости от используемого конструктора. Очередь с приоритетами не допускает null элементы. Очередь с приоритетами, использующая естественный порядок, также не допускает вставки несопоставимых объектов (это может привести к ClassCastException).

Голова этой очереди — это наименьший элемент с точки зрения указанного порядка. Если несколько элементов имеют одинаковое наименьшее значение, голова — это один из этих элементов; такие связи разрываются произвольно. Операции извлечения из очереди poll, remove, peek, и element обращаются к элементу в голове очереди.

Очередь с приоритетами безгранична, но имеет внутреннюю емкость, определяющую размер массива, используемого для хранения элементов в очереди. Она всегда не меньше размера очереди. По мере добавления элементов в очередь с приоритетами ее емкость автоматически увеличивается. Подробности политики роста не указаны.

Этот класс и его итератор реализуют все необязательные методы интерфейсов Collection и Iterator. Итератор, предоставленный в методе iterator(), и разделитель, предоставленный в методе spliterator(), не гарантируют прохождения элементов очереди с приоритетами в определённом порядке. Если вам нужна упорядоченная обработка, рассмотрите использование Arrays.sort(pq.toArray()).

Обратите внимание, что эта реализация не синхронизирована. Несколько потоков не должны одновременно обращаться к экземпляру PriorityQueue , если какой-либо из потоков изменяет очередь. Вместо этого используйте потокобезопасный класс PriorityBlockingQueue.

Примечание к реализации: эта реализация обеспечивает время O(log(n)) для методов очереди (offer, poll, remove() и add); линейное время для методов remove(Object) и contains(Object); и постоянное время для методов извлечения (peek, element, и size).

Этот класс является членом Фреймворка коллекций Java.

Since:
1.5
См. также:
Сериализованная форма

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

Конструктор Описание
PriorityQueue()

Создаёт очередь PriorityQueue с начальной емкостью по умолчанию (11), которая упорядочивает элементы в соответствии с их естественным порядком.
PriorityQueue​(int initialCapacity)

Создаёт очередь PriorityQueue с указанной начальной емкостью, которая упорядочивает элементы в соответствии с их естественным порядком.
PriorityQueue​(int initialCapacity, Comparator<? super E> comparator)

Создаёт очередь PriorityQueue с указанной начальной емкостью, которая упорядочивает элементы в соответствии с указанным компаратором.
PriorityQueue​(Collection<? extends E> c)

Создаёт очередь PriorityQueue, содержащую элементы в указанной коллекции.
PriorityQueue​(Comparator<? super E> comparator)

Создаёт очередь PriorityQueue с начальной емкостью по умолчанию, элементы которой упорядочены в соответствии с указанным компаратором.
PriorityQueue​(PriorityQueue<? extends E> c)

Создаёт очередь PriorityQueue, содержащую элементы в указанной очереди с приоритетами.
PriorityQueue​(SortedSet<? extends E> c)

Создаёт очередь PriorityQueue, содержащую элементы в указанном упорядоченном наборе.

Методы

Модификатор и тип Метод Описание
boolean add​(E e)

Вставляет указанный элемент в эту очередь с приоритетами.
void clear()

Удаляет все элементы из этой очереди с приоритетами.
Comparator<? super E> comparator()

Возвращает компаратор, используемый для упорядочения элементов в этой очереди, или null , если эта очередь упорядочена в соответствии с естественным порядком своих элементов.
boolean contains​(Object o)

Возвращает true , если эта очередь содержит указанный элемент.
void forEach​(Consumer<? super E> action)

Выполняет заданное действие для каждого элемента Iterable , пока все элементы не будут обработаны или действие не выбросит исключение.
Iterator<E> iterator()

Возвращает итератор по элементам в этой очереди.
boolean offer​(E e)

Вставляет указанный элемент в эту очередь с приоритетами.
boolean remove​(Object o)

Удаляет единственный экземпляр указанного элемента из этой очереди, если он присутствует.
boolean removeAll​(Collection<?> c)

Удаляет все элементы этой коллекции, которые также содержатся в указанной коллекции (необязательная операция).
boolean removeIf​(Predicate<? super E> filter)

Удаляет все элементы этой коллекции, удовлетворяющие заданному предикату.
boolean retainAll​(Collection<?> c)

Сохраняет только элементы в этой коллекции, которые содержатся в указанной коллекции (необязательная операция).
Spliterator<E> spliterator()

Создаёт отложенную и быстропроверяющую Spliterator над элементами в этой очереди.
Object[] toArray()

Возвращает массив, содержащий все элементы в этой очереди.
<T> T[] toArray​(T[] a)

Возвращает массив, содержащий все элементы в этой очереди; тип возвращаемого массива — это тип указанного массива.

Методы, объявленные в классе java.util.AbstractQueue

addAll, element, remove

Методы, объявленные в классе java.util.AbstractCollection

containsAll, isEmpty, toString

Методы, объявленные в классе java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Методы, объявленные в интерфейсе java.util.Collection

containsAll, equals, hashCode, isEmpty, parallelStream, size, stream, toArray

Методы, объявленные в интерфейсе java.util.Queue

peek, poll

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

PriorityQueue

public PriorityQueue()

Создаёт очередь с приоритетами PriorityQueue с начальной ёмкостью по умолчанию (11), которая сортирует элементы в соответствии с их естественным порядком.

PriorityQueue

public PriorityQueue(int initialCapacity)

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

Параметры:
initialCapacity - начальная ёмкость для этой очереди с приоритетами
Исключения:
IllegalArgumentException - если initialCapacity меньше 1

PriorityQueue

public PriorityQueue(Comparator<? super E> comparator)

Создаёт очередь с приоритетами PriorityQueue с начальной ёмкостью по умолчанию, элементы которой упорядочены в соответствии с указанным компаратором.

Параметры:
comparator - компаратор, который будет использоваться для упорядочения этой очереди с приоритетами. Если null, будет использован естественный порядок элементов.
С тех пор:
1.8

PriorityQueue

public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator)

Создаёт очередь с приоритетами PriorityQueue с указанной начальной ёмкостью, элементы которой упорядочены в соответствии с указанным компаратором.

Параметры:
initialCapacity - начальная ёмкость для этой очереди с приоритетами
comparator - компаратор, который будет использоваться для упорядочения этой очереди с приоритетами. Если null, будет использован естественный порядок элементов.
Исключения:
IllegalArgumentException - если initialCapacity меньше 1

PriorityQueue

public PriorityQueue(Collection<? extends E> c)

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

Параметры:
c - коллекция, элементы которой должны быть помещены в эту очередь с приоритетами
Исключения:
ClassCastException - если элементы указанной коллекции нельзя сравнить друг с другом в соответствии с порядком очереди с приоритетами
NullPointerException - если указанная коллекция или любой из её элементов равны null

PriorityQueue

public PriorityQueue(PriorityQueue<? extends E> c)

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

Параметры:
c - очередь с приоритетами, элементы которой должны быть помещены в эту очередь с приоритетами
Исключения:
ClassCastException - если элементы c нельзя сравнить друг с другом в соответствии с порядком c
NullPointerException - если указанная очередь с приоритетами или любой из её элементов равны null

PriorityQueue

public PriorityQueue(SortedSet<? extends E> c)

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

Параметры:
c - упорядоченный набор, элементы которого должны быть помещены в эту очередь с приоритетами
Исключения:
ClassCastException - если элементы указанного упорядоченного набора нельзя сравнить друг с другом в соответствии с порядком упорядоченного набора
NullPointerException - если указанный упорядоченный набор или любой из его элементов равны null

Методы

add

public boolean add(E e)

Вставляет указанный элемент в эту очередь с приоритетом.

Указано в:
add в интерфейсе Collection<E>
Указано в:
add в интерфейсе Queue<E>
Переопределяет:
add в классе AbstractQueue<E>
Параметры:
e - элемент для добавления
Возвращает:
true (как указано в Collection.add(E))
Исключения:
ClassCastException - если указанный элемент нельзя сравнить с элементами, в настоящее время находящимися в этой очереди с приоритетом, согласно порядку сортировки очереди
NullPointerException - если указанный элемент равен null

offer

public boolean offer(E e)

Вставляет указанный элемент в эту очередь с приоритетом.

Указано в:
offer в интерфейсе Queue<E>
Параметры:
e - элемент для добавления
Возвращает:
true (как указано в Queue.offer(E))
Исключения:
ClassCastException - если указанный элемент нельзя сравнить с элементами, в настоящее время находящимися в этой очереди с приоритетом, согласно порядку сортировки очереди
NullPointerException - если указанный элемент равен null

remove

public boolean remove(Object o)

Удаляет один экземпляр указанного элемента из этой очереди, если он присутствует. Более формально, удаляет элемент e такой, что o.equals(e), если эта очередь содержит один или несколько таких элементов. Возвращает true тогда и только тогда, когда эта очередь содержала указанный элемент (или, что эквивалентно, если эта очередь изменилась в результате вызова).

Указано в:
remove в интерфейсе Collection<E>
Переопределяет:
remove в классе AbstractCollection<E>
Параметры:
o - элемент, который необходимо удалить из этой очереди, если он присутствует
Возвращает:
true если эта очередь изменилась в результате вызова

contains

public boolean contains(Object o)

Возвращает true если эта очередь содержит указанный элемент. Более формально, возвращает true тогда и только тогда, когда эта очередь содержит по крайней мере один элемент e такой, что o.equals(e).

Указано в:
contains в интерфейсе Collection<E>
Переопределяет:
contains в классе AbstractCollection<E>
Параметры:
o - объект, который необходимо проверить на наличие в этой очереди
Возвращает:
true если эта очередь содержит указанный элемент

toArray

public Object[] toArray()

Возвращает массив, содержащий все элементы в этой очереди. Элементы не упорядочены особым образом.

Возвращаемый массив будет «безопасным» в том смысле, что к нему не сохраняются ссылки этой очередью. (Другими словами, этот метод должен выделить новый массив). Таким образом, вызывающая сторона свободна изменять возвращаемый массив.

Этот метод действует как мост между API на основе массивов и API на основе коллекций.

Указано в:
toArray в интерфейсе Collection<E>
Переопределяет:
toArray в классе AbstractCollection<E>
Возвращает:
массив, содержащий все элементы в этой очереди

toArray

public <T> T[] toArray(T[] a)

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

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

Как и метод toArray(), этот метод служит мостом между API на основе массивов и API на основе коллекций. Кроме того, этот метод позволяет точно контролировать тип выполнения выходного массива и может в определённых ситуациях использоваться для экономии затрат на выделение памяти.

Предположим, x — это очередь, известная тем, что содержит только строки. Следующий код может быть использован для выгрузки очереди в новый выделенный массив типа String: 

String[] y = x.toArray(new String[0]);
Обратите внимание, что toArray(new Object[0]) идентичен по функции toArray().
Указано в:
toArray в интерфейсе Collection<E>
Переопределяет:
toArray в классе AbstractCollection<E>
Параметры типа:
T - тип компонента массива, содержащего коллекцию
Параметры:
a - массив, в который должны быть помещены элементы очереди, если он достаточно большой; в противном случае для этой цели выделяется новый массив того же типа выполнения.
Возвращает:
массив, содержащий все элементы в этой очереди
Исключения:
ArrayStoreException - если тип выполнения указанного массива не является надтипом типа выполнения каждого элемента в этой очереди
NullPointerException - если указанный массив равен null

iterator

public Iterator<E> iterator()

Возвращает итератор по элементам в этой очереди. Итератор не возвращает элементы в каком-либо конкретном порядке.

Указано в:
iterator в интерфейсе Collection<E>
Указано в:
iterator в интерфейсе Iterable<E>
Указано в:
iterator в классе AbstractCollection<E>
Возвращает:
итератор по элементам в этой очереди

clear

public void clear()

Удаляет все элементы из этой очереди с приоритетом. Очередь будет пустой после возврата этого вызова.

Указано в:
clear в интерфейсе Collection<E>
Переопределяет:
clear в классе AbstractQueue<E>

comparator

public Comparator<? super E> comparator()

Возвращает компаратор, используемый для упорядочивания элементов в этой очереди, или null если эта очередь отсортирована в соответствии с естественным порядком своих элементов.

Возвращает:
компаратор, используемый для упорядочивания этой очереди, или null если эта очередь отсортирована в соответствии с естественным порядком своих элементов

spliterator

public final Spliterator<E> spliterator()

Создаёт поздне-связанный и быстропроверяющий Spliterator по элементам в этой очереди. Spliterator не проходит элементы в каком-либо конкретном порядке (характеристика ORDERED не сообщается).

Spliterator сообщает Spliterator.SIZED, Spliterator.SUBSIZED и Spliterator.NONNULL. Переопределяющие реализации должны документировать оповещение об дополнительных характеристиках.

Указано в:
spliterator в интерфейсе Collection<E>
Указано в:
spliterator в интерфейсе Iterable<E>
Возвращает:
Spliterator по элементам в этой очереди
С:
1.8

removeIf

public boolean removeIf(Predicate<? super E> filter)

Описание скопировано из интерфейса: Collection

Удаляет все элементы этой коллекции, удовлетворяющие заданному предикату. Ошибки или исключения времени выполнения, возникающие во время итерации или предикатом, передаются вызывающей стороне.

Указано в:
removeIf в интерфейсе Collection<E>
Параметры:
filter - предикат, который возвращает true для элементов, подлежащих удалению
Возвращает:
true если какие-либо элементы были удалены
Исключения:
NullPointerException - если указанный фильтр равен null

removeAll

public boolean removeAll(Collection<?> c)

Описание скопировано из класса: AbstractCollection

Удаляет все элементы этой коллекции, которые также содержатся в указанной коллекции (необязательная операция). После возврата этого вызова эта коллекция не будет содержать общих элементов с указанной коллекцией.

Указано в:
removeAll в интерфейсе Collection<E>
Переопределяет:
removeAll в классе AbstractCollection<E>
Параметры:
c - коллекция, содержащая элементы, которые необходимо удалить из этой коллекции
Возвращает:
true если эта коллекция изменилась в результате вызова
Исключения:
NullPointerException - если эта коллекция содержит один или несколько элементов null, а указанная коллекция не поддерживает элементы null (необязательно), или если указанная коллекция равна null
См. также:
AbstractCollection.remove(Object), AbstractCollection.contains(Object)

retainAll

public boolean retainAll(Collection<?> c)

Описание скопировано из класса: AbstractCollection

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

Указано в:
retainAll в интерфейсе Collection<E>
Переопределяет:
retainAll в классе AbstractCollection<E>
Параметры:
c — коллекция, содержащая элементы, которые должны быть сохранены в этой коллекции
Возвращает:
true если эта коллекция изменилась в результате вызова
Исключение:
NullPointerException — если эта коллекция содержит один или несколько нулевых элементов, а указанная коллекция не допускает нулевых элементов (необязательно), или если указанная коллекция равна null
См. также:
AbstractCollection.remove(Object), AbstractCollection.contains(Object)

forEach

public void forEach(Consumer<? super E> action)

Описание скопировано из интерфейса: Iterable

Выполняет заданное действие для каждого элемента Iterable до тех пор, пока все элементы не будут обработаны или действие не выбросит исключение. Действия выполняются в порядке итерации, если этот порядок указан. Исключения, выброшенные действием, передаются вызывающему объекту.

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

Указано в:
forEach в интерфейсе Iterable<E>
Параметры:
action — действие, которое должно выполняться для каждого элемента
Исключение:
NullPointerException — если указанное действие равно null

© 1993, 2020, Oracle and/or its affiliates. All rights reserved.
Documentation extracted from Debian's OpenJDK Development Kit package.
Licensed under the GNU General Public License, version 2, with the Classpath Exception.
Various third party code in OpenJDK is licensed under different licenses (see Debian package).
Java and OpenJDK are trademarks or registered trademarks of Oracle and/or its affiliates.
https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html

Spec-Zone .ru
спецификации, руководства, описания, API