Класс 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()`	Создаёт очередь приоритетов с начальной емкостью по умолчанию (11), которая упорядочивает свои элементы в соответствии с их естественным порядком.
`PriorityQueue(int initialCapacity)`	Создаёт очередь приоритетов с заданной начальной емкостью, которая упорядочивает свои элементы в соответствии с их естественным порядком.
`PriorityQueue(int initialCapacity, Comparator<? super E> comparator)`	Создаёт очередь приоритетов с заданной начальной емкостью, которая упорядочивает свои элементы в соответствии с указанным компаратором.
`PriorityQueue(Collection<? extends E> c)`	Создаёт очередь приоритетов, содержащую элементы в указанной коллекции.
`PriorityQueue(Comparator<? super E> comparator)`	Создаёт очередь приоритетов с начальной емкостью по умолчанию, элементы которой упорядочены в соответствии с указанным компаратором.
`PriorityQueue(PriorityQueue<? extends E> c)`	Создаёт очередь приоритетов, содержащую элементы в указанной очереди приоритетов.
`PriorityQueue(SortedSet<? extends E> c)`	Создаёт очередь приоритетов, содержащую элементы в указанном упорядоченном наборе.

Краткое описание методов

Модификатор и тип	Метод	Описание
`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

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

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

peek

public E peek()

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

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

Определено в:: peek в интерфейсе Queue<E>
Возвращает:: голову этой очереди или 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.

Определено в:: 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().

Указано в:: toArray в интерфейсе Collection<E>
Переопределяет:: toArray в классе AbstractCollection<E>
Параметры типа:: T - тип компонентов массива, содержащего коллекцию
Параметры:: a - массив, в который должны быть помещены элементы очереди, если он достаточно велик; в противном случае для этой цели выделяется новый массив того же типа runtime.
Возвращает:: массив, содержащий все элементы в этой очереди
Исключения:: ArrayStoreException - если тип выполнения указанного массива не является надтипом типа выполнения каждого элемента в этой очереди; NullPointerException - если указанный массив равен null

iterator

public Iterator<E> iterator()

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

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

size

public int size()

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

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

Указано в:: size в интерфейсе Collection<E>
Возвращает:: количество элементов в этой коллекции

clear

public void clear()

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

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

poll

public E poll()

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

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

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

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

См. также:

retainAll

public boolean retainAll(Collection<?> c)

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

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

Указано в:

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

Переопределяет:

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

Параметры:

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

Возвращает:

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

Исключения:

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

См. также:

forEach

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

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

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

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

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

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