Класс PriorityQueue<E>

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

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

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

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

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

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

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

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

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()

Определено в:

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

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

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

Возвращает:

массив, содержащий все элементы в этой очереди

toArray

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

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

Определено в:

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

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

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

Параметры типа:

T - тип выполнения массива, который должен содержать коллекцию

Параметры:

a - массив, в который должны быть помещены элементы очереди, если он достаточно большой; в противном случае для этой цели выделяется новый массив того же типа выполнения.

Возвращает:

массив, содержащий все элементы в этой очереди

Исключения:

ArrayStoreException - если тип выполнения указанного массива не является супертипом типа выполнения каждого элемента в этой очереди

NullPointerException - если указанный массив имеет значение null

iterator

public Iterator<E> iterator()

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

Определено в:

iterator в интерфейсе Iterable<E>

Определено в:

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

Определено в:

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

Возвращает:

итератор по элементам в этой очереди

size

public int size()

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

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

Указано:

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

Указано:

size в классе AbstractCollection<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 в интерфейсе Iterable<E>

Указано:

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

Возвращает:

Spliterator над элементами в этой очереди

С:

1.8