Класс PriorityQueue<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractQueue<E>

java.util.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, предоставляемый в методе spliterator(), не гарантируют обход элементов очереди приоритетов в каком-либо определенном порядке. Если вам нужен упорядоченный обход, рассмотрите использование Arrays.sort(pq.toArray()).

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

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

Этот класс является членом Java Collections Framework.

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)`	Вставляет указанный элемент в эту очередь приоритетов.
`E`	`peek()`	Возвращает, но не удаляет, голову этой очереди или возвращает `null` , если эта очередь пуста.
`E`	`poll()`	Возвращает и удаляет голову этой очереди или возвращает `null` , если эта очередь пуста.
`boolean`	`remove(Object o)`	Удаляет один экземпляр указанного элемента из этой очереди, если он присутствует.
`boolean`	`removeAll(Collection<?> c)`	Удаляет все элементы этой коллекции, которые также содержатся в указанной коллекции (необязательная операция).
`boolean`	`removeIf(Predicate<? super E> filter)`	Удаляет все элементы этой коллекции, которые удовлетворяют заданному предикату.
`boolean`	`retainAll(Collection<?> c)`	Сохраняет только элементы в этой коллекции, которые содержатся в указанной коллекции (необязательная операция).
`int`	`size()`	Возвращает количество элементов в этой коллекции.
`final 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, stream, toArray

Подробное описание конструкторов

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

Подробное описание методов

добавить

public boolean add(E e)

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

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

внести

public boolean offer(E e)

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

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

получить

public E peek()

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

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

Унаследован от:: peek в интерфейсе Queue<E>
Возвращает:: голову этой очереди или null, если эта очередь пуста

удалить

public boolean remove(Object o)

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

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

содержит

public boolean contains(Object o)

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

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

toArray

public Object[] toArray()

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

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

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

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

toArray

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

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

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

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

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

 String[] y = x.toArray(new String[0]);

Обратите внимание, что toArray(new Object[0]) выполняет идентичные функции, что и toArray().

Specified by:: toArray в интерфейсе Collection<E>
Overrides:: toArray в классе AbstractCollection<E>
Type Parameters:: T - тип компонентов массива, содержащего коллекцию
Parameters:: a - массив, в который будут помещены элементы очереди, если он достаточно большой; в противном случае, для этой цели выделяется новый массив того же типа.
Returns:: массив, содержащий все элементы в этой очереди
Throws:: ArrayStoreException - если тип указанного массива не является супертипом типа каждого элемента в этой очереди; NullPointerException - если указанный массив null

iterator

public Iterator<E> iterator()

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

Specified by:: iterator в интерфейсе Collection<E>
Specified by:: iterator в интерфейсе Iterable<E>
Specified by:: iterator в классе AbstractCollection<E>
Returns:: итератор по элементам в этой очереди

size

public int size()

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

Возвращает количество элементов в этой коллекции. Если эта коллекция содержит более Integer.MAX_VALUE элементов, возвращает Integer.MAX_VALUE.

Specified by:: size в интерфейсе Collection<E>
Returns:: количество элементов в этой коллекции

clear

public void clear()

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

Specified by:: clear в интерфейсе Collection<E>
Overrides:: clear в классе AbstractQueue<E>

poll

public E poll()

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

Возвращает и удаляет голову этой очереди или возвращает null если эта очередь пуста.

Specified by:: poll в интерфейсе Queue<E>
Returns:: голова этой очереди или null если эта очередь пуста

comparator

public Comparator<? super E> comparator()

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

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

spliterator

public final Spliterator<E> spliterator()

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

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

Specified by:: spliterator в интерфейсе Collection<E>
Specified by:: spliterator в интерфейсе Iterable<E>
Returns:: Spliterator по элементам в этой очереди
Since:: 1.8

removeIf

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

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

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

Specified by:: removeIf в интерфейсе Collection<E>
Parameters:: filter - предикат, который возвращает true для удаляемых элементов
Returns:: true если какие-либо элементы были удалены
Throws:: NullPointerException - если указанный фильтр null

removeAll

public boolean removeAll(Collection<?> c)

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

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

Specified by:

removeAll в интерфейсе Collection<E>

Overrides:

removeAll в классе AbstractCollection<E>

Parameters:

c - коллекция, содержащая элементы, которые нужно удалить из этой коллекции

Returns:

true если эта коллекция изменилась в результате вызова

Throws:

NullPointerException - если эта коллекция содержит один или несколько null-элементов, а указанная коллекция не поддерживает null-элементы (дополнительное ограничение) или если указанная коллекция null

See Also:

retainAll

public boolean retainAll(Collection<?> c)

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

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

Specified by:

retainAll в интерфейсе Collection<E>

Overrides:

retainAll в классе AbstractCollection<E>

Parameters:

c - коллекция, содержащая элементы, которые нужно сохранить в этой коллекции

Returns:

true если эта коллекция изменилась в результате вызова

Throws:

NullPointerException - если эта коллекция содержит один или несколько null-элементов, а указанная коллекция не допускает null-элементов (дополнительное ограничение) или если указанная коллекция null

See Also:

forEach

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

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

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

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

Specified by:: forEach в интерфейсе Iterable<E>
Parameters:: action - действие, которое нужно выполнить для каждого элемента
Throws:: NullPointerException - если указанное действие null

© 1993, 2023, 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/21/docs/api/java.base/java/util/PriorityQueue.html