Modifier and Type	Class and Description
private class	PriorityQueue.Itr
pack-priv class	PriorityQueue.PriorityQueueSpliterator

Modifier and Type	Field and Description
private final Comparator<? super E>	comparator The comparator, or null if priority queue uses elements' natural ordering.
private static final int	DEFAULT_INITIAL_CAPACITY
pack-priv transient int	modCount The number of times this priority queue has been structurally modified.
pack-priv transient Object[]	queue Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+1] and queue[2(n+1)].
private static final long	serialVersionUID
pack-priv int	size The number of elements in the priority queue.

Access	Constructor and Description
public	PriorityQueue() Creates a `PriorityQueue` with the default initial capacity (11) that orders its elements according to their natural ordering.
public	PriorityQueue(int the initial capacity for this priority queue initialCapacity) Creates a `PriorityQueue` with the specified initial capacity that orders its elements according to their natural ordering.
public	PriorityQueue(Comparator<? super E> the comparator that will be used to order this priority queue. If `null`, the natural ordering of the elements will be used. comparator) Creates a `PriorityQueue` with the default initial capacity and whose elements are ordered according to the specified comparator.
public	PriorityQueue(int the initial capacity for this priority queue initialCapacity, Comparator<? super E> the comparator that will be used to order this priority queue. If `null`, the natural ordering of the elements will be used. comparator) Creates a `PriorityQueue` with the specified initial capacity that orders its elements according to the specified comparator.
public	PriorityQueue(Collection<? extends E> the collection whose elements are to be placed into this priority queue c) Creates a `PriorityQueue` containing the elements in the specified collection.
public	PriorityQueue(PriorityQueue<? extends E> the priority queue whose elements are to be placed into this priority queue c) Creates a `PriorityQueue` containing the elements in the specified priority queue.
public	PriorityQueue(SortedSet<? extends E> the sorted set whose elements are to be placed into this priority queue c) Creates a `PriorityQueue` containing the elements in the specified sorted set.

Method Summary

Modifier and Type	Method and Description
public boolean	Returns: `true` (as specified by `Collection#add`) add(E the element to add e) Overrides java.util.AbstractQueue.add. Implements java.util.Queue.add, java.util.Collection.add. Inserts the specified element into this priority queue.
private boolean	bulkRemove(Predicate<? super E> filter) Implementation of bulk remove methods.
public void	clear() Overrides java.util.AbstractQueue.clear. Implements java.util.Collection.clear. Removes all of the elements from this priority queue.
public Comparator<? super E>	Returns: the comparator used to order this queue, or `null` if this queue is sorted according to the natural ordering of its elements comparator() Returns the comparator used to order the elements in this queue, or `null` if this queue is sorted according to the natural ordering of its elements.
public boolean	Returns: `true` if this queue contains the specified element contains(Object object to be checked for containment in this queue o) Overrides java.util.AbstractCollection.contains. Implements java.util.Collection.contains. Returns `true` if this queue contains the specified element.
private static Object[]	ensureNonEmpty(Object[] es) Ensures that queue[0] exists, helping peek() and poll().
public void	forEach(Consumer<? super E> The action to be performed for each element action) Overrides default java.lang.Iterable.forEach. Performs the given action for each element of the `Iterable` until all elements have been processed or the action throws an exception.
private void	grow(int the desired minimum capacity minCapacity) Increases the capacity of the array.
private void	heapify() Establishes the heap invariant (described above) in the entire tree, assuming nothing about the order of the elements prior to the call.
private int	indexOf(Object o)
private void	initElementsFromCollection(Collection<? extends E> c)
private void	initFromCollection(Collection<? extends E> the collection c) Initializes queue array with elements from the given Collection.
private void	initFromPriorityQueue(PriorityQueue<? extends E> c)
private static boolean	isClear(long[] bits, int i)
public Iterator<E>	Returns: an iterator over the elements in this queue iterator() Implements abstract java.util.AbstractCollection.iterator. Implements java.util.Collection.iterator. Returns an iterator over the elements in this queue.
private static long[]	nBits(int n)
public boolean	Returns: `true` (as specified by `Queue#offer`) offer(E the element to add e) Implements java.util.Queue.offer. Inserts the specified element into this priority queue.
public E	peek() Implements java.util.Queue.peek. Retrieves, but does not remove, the head of this queue, or returns `null` if this queue is empty.
public E	poll() Implements java.util.Queue.poll. Retrieves and removes the head of this queue, or returns `null` if this queue is empty.
private void	readObject(ObjectInputStream the stream s) Reconstitutes the `PriorityQueue` instance from a stream (that is, deserializes it).
public boolean	Returns: `true` if this queue changed as a result of the call remove(Object element to be removed from this queue, if present o) Overrides java.util.AbstractCollection.remove. Implements java.util.Collection.remove. Removes a single instance of the specified element from this queue, if it is present.
public boolean	removeAll(Collection<?> collection containing elements to be removed from this collection c) Overrides java.util.AbstractCollection.removeAll. Implements java.util.Collection.removeAll. Removes all of this collection's elements that are also contained in the specified collection (optional operation).
pack-priv E	removeAt(int i) Removes the ith element from queue.
pack-priv void	removeEq(Object element to be removed from this queue, if present o) Identity-based version for use in Itr.remove.
public boolean	removeIf(Predicate<? super E> a predicate which returns `true` for elements to be removed filter) Overrides default java.util.Collection.removeIf. Removes all of the elements of this collection that satisfy the given predicate (optional operation).
public boolean	retainAll(Collection<?> collection containing elements to be retained in this collection c) Overrides java.util.AbstractCollection.retainAll. Implements java.util.Collection.retainAll. Retains only the elements in this collection that are contained in the specified collection (optional operation).
private static void	setBit(long[] bits, int i)
private void	siftDown(int the position to fill k, E the item to insert x) Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf.
private static <T> void	siftDownComparable(int k, T x, Object[] es, int n)
private static <T> void	siftDownUsingComparator(int k, T x, Object[] es, int n, Comparator<? super T> cmp)
private void	siftUp(int the position to fill k, E the item to insert x) Inserts item x at position k, maintaining heap invariant by promoting x up the tree until it is greater than or equal to its parent, or is the root.
private static <T> void	siftUpComparable(int k, T x, Object[] es)
private static <T> void	siftUpUsingComparator(int k, T x, Object[] es, Comparator<? super T> cmp)
public int	size() Implements abstract java.util.AbstractCollection.size. Implements java.util.Collection.size. Returns the number of elements in this collection.
public final Spliterator<E>	Returns: a `Spliterator` over the elements in this queue spliterator() Overrides default java.util.Collection.spliterator. Creates a late-binding and fail-fast `Spliterator` over the elements in this queue.
public Object[]	Returns: an array containing all of the elements in this queue toArray() Overrides java.util.AbstractCollection.toArray. Implements java.util.Collection.toArray. Returns an array containing all of the elements in this queue.
public <T> T[]	Returns: an array containing all of the elements in this queue toArray(T[] the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose. a) Overrides java.util.AbstractCollection.toArray. Implements java.util.Collection.toArray. Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.
private void	writeObject(ObjectOutputStream the stream s) Saves this queue to a stream (that is, serializes it).

Inherited from java.util.AbstractQueue:: addAll element remove

Field Detail

comparator	back to summary
private final Comparator<? super E> comparator The comparator, or null if priority queue uses elements' natural ordering. Annotations @SuppressWarnings:serial

DEFAULT_INITIAL_CAPACITY	back to summary
private static final int DEFAULT_INITIAL_CAPACITY

modCount	back to summary
pack-priv transient int modCount The number of times this priority queue has been structurally modified. See AbstractList for gory details.

queue	back to summary
pack-priv transient Object[] queue Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+1] and queue[2(n+1)]. The priority queue is ordered by comparator, or by the elements' natural ordering, if comparator is null: For each node n in the heap and each descendant d of n, n <= d. The element with the lowest value is in queue[0], assuming the queue is nonempty.

queue

back to summary

pack-priv transient Object[] queue

Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The priority queue is ordered by comparator, or by the elements' natural ordering, if comparator is null: For each node n in the heap and each descendant d of n, n <= d. The element with the lowest value is in queue[0], assuming the queue is nonempty.

serialVersionUID	back to summary
private static final long serialVersionUID Annotations @Serial

size	back to summary
pack-priv int size The number of elements in the priority queue.

Constructor Detail

PriorityQueue	back to summary
public PriorityQueue() Creates a `PriorityQueue` with the default initial capacity (11) that orders its elements according to their natural ordering.

PriorityQueue back to summary

PriorityQueue	back to summary
public PriorityQueue(int initialCapacity) Creates a `PriorityQueue` with the specified initial capacity that orders its elements according to their natural ordering. Parameters initialCapacity:int the initial capacity for this priority queue Exceptions IllegalArgumentException: if `initialCapacity` is less than 1

public PriorityQueue(int initialCapacity)

Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.

Parameters

initialCapacity:int: the initial capacity for this priority queue

Exceptions

IllegalArgumentException:: if initialCapacity is less than 1

PriorityQueue back to summary

PriorityQueue	back to summary
public PriorityQueue(Comparator<? super E> comparator) Creates a `PriorityQueue` with the default initial capacity and whose elements are ordered according to the specified comparator. Parameters comparator:Comparator<? super E> the comparator that will be used to order this priority queue. If `null`, the natural ordering of the elements will be used. Since 1.8

public PriorityQueue(Comparator<? super E> comparator)

Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator.

Parameters

comparator:Comparator<? super E>: the comparator that will be used to order this priority queue. If null, the natural ordering of the elements will be used.

Since

1.8

PriorityQueue back to summary

PriorityQueue	back to summary
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) Creates a `PriorityQueue` with the specified initial capacity that orders its elements according to the specified comparator. Parameters initialCapacity:int the initial capacity for this priority queue comparator:Comparator<? super E> the comparator that will be used to order this priority queue. If `null`, the natural ordering of the elements will be used. Exceptions IllegalArgumentException: if `initialCapacity` is less than 1

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

Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

Parameters

initialCapacity:int: the initial capacity for this priority queue
comparator:Comparator<? super E>: the comparator that will be used to order this priority queue. If null, the natural ordering of the elements will be used.

Exceptions

IllegalArgumentException:: if initialCapacity is less than 1

PriorityQueue back to summary

PriorityQueue	back to summary
public PriorityQueue(Collection<? extends E> c) Creates a `PriorityQueue` containing the elements in the specified collection. If the specified collection is an instance of a `SortedSet` or is another `PriorityQueue`, this priority queue will be ordered according to the same ordering. Otherwise, this priority queue will be ordered according to the natural ordering of its elements. Parameters c:Collection<? extends E> the collection whose elements are to be placed into this priority queue Exceptions ClassCastException: if elements of the specified collection cannot be compared to one another according to the priority queue's ordering NullPointerException: if the specified collection or any of its elements are null

public PriorityQueue(Collection<? extends E> c)

Creates a PriorityQueue containing the elements in the specified collection. If the specified collection is an instance of a SortedSet or is another PriorityQueue, this priority queue will be ordered according to the same ordering. Otherwise, this priority queue will be ordered according to the natural ordering of its elements.

Parameters

c:Collection<? extends E>: the collection whose elements are to be placed into this priority queue

Exceptions

ClassCastException:: if elements of the specified collection cannot be compared to one another according to the priority queue's ordering
NullPointerException:: if the specified collection or any of its elements are null

PriorityQueue back to summary

PriorityQueue	back to summary
public PriorityQueue(PriorityQueue<? extends E> c) Creates a `PriorityQueue` containing the elements in the specified priority queue. This priority queue will be ordered according to the same ordering as the given priority queue. Parameters c:PriorityQueue<? extends E> the priority queue whose elements are to be placed into this priority queue Exceptions ClassCastException: if elements of `c` cannot be compared to one another according to `c`'s ordering NullPointerException: if the specified priority queue or any of its elements are null

public PriorityQueue(PriorityQueue<? extends E> c)

Creates a PriorityQueue containing the elements in the specified priority queue. This priority queue will be ordered according to the same ordering as the given priority queue.

Parameters

c:PriorityQueue<? extends E>: the priority queue whose elements are to be placed into this priority queue

Exceptions

ClassCastException:: if elements of c cannot be compared to one another according to c's ordering
NullPointerException:: if the specified priority queue or any of its elements are null

PriorityQueue back to summary

PriorityQueue	back to summary
public PriorityQueue(SortedSet<? extends E> c) Creates a `PriorityQueue` containing the elements in the specified sorted set. This priority queue will be ordered according to the same ordering as the given sorted set. Parameters c:SortedSet<? extends E> the sorted set whose elements are to be placed into this priority queue Exceptions ClassCastException: if elements of the specified sorted set cannot be compared to one another according to the sorted set's ordering NullPointerException: if the specified sorted set or any of its elements are null

public PriorityQueue(SortedSet<? extends E> c)

Creates a PriorityQueue containing the elements in the specified sorted set. This priority queue will be ordered according to the same ordering as the given sorted set.

Parameters

c:SortedSet<? extends E>: the sorted set whose elements are to be placed into this priority queue

Exceptions

ClassCastException:: if elements of the specified sorted set cannot be compared to one another according to the sorted set's ordering
NullPointerException:: if the specified sorted set or any of its elements are null

Method Detail

add back to summary

add	back to summary
public boolean add(E e) Overrides java.util.AbstractQueue.add. Implements java.util.Queue.add, java.util.Collection.add. Inserts the specified element into this priority queue. Parameters e:E Doc from java.util.AbstractQueue.add. the element to add Returns:boolean `true` (as specified by `Collection#add`) Exceptions ClassCastException: if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering NullPointerException: if the specified element is null

public boolean add(E e)

Overrides java.util.AbstractQueue.add.

Implements java.util.Queue.add, java.util.Collection.add.

Inserts the specified element into this priority queue.

Parameters

e:E

Doc from java.util.AbstractQueue.add.

the element to add

Returns:boolean

true (as specified by Collection#add)

Exceptions

ClassCastException:: if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering
NullPointerException:: if the specified element is null

bulkRemove	back to summary
private boolean bulkRemove(Predicate<? super E> filter) Implementation of bulk remove methods.

clear	back to summary
public void clear() Overrides java.util.AbstractQueue.clear. Implements java.util.Collection.clear. Removes all of the elements from this priority queue. The queue will be empty after this call returns.

clear

back to summary

public void clear()

Overrides java.util.AbstractQueue.clear.

Implements java.util.Collection.clear.

Removes all of the elements from this priority queue. The queue will be empty after this call returns.

comparator back to summary

comparator	back to summary
public Comparator<? super E> comparator() Returns the comparator used to order the elements in this queue, or `null` if this queue is sorted according to the natural ordering of its elements. Returns:Comparator<? super E> the comparator used to order this queue, or `null` if this queue is sorted according to the natural ordering of its elements

public Comparator<? super E> comparator()

Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements.

Returns:Comparator<? super E>: the comparator used to order this queue, or null if this queue is sorted according to the natural ordering of its elements

contains back to summary

contains	back to summary
public boolean contains(Object o) Overrides java.util.AbstractCollection.contains. Implements java.util.Collection.contains. Returns `true` if this queue contains the specified element. More formally, returns `true` if and only if this queue contains at least one element `e` such that `o.equals(e)`. Parameters o:Object object to be checked for containment in this queue Returns:boolean `true` if this queue contains the specified element

public boolean contains(Object o)

Overrides java.util.AbstractCollection.contains.

Implements java.util.Collection.contains.

Returns true if this queue contains the specified element. More formally, returns true if and only if this queue contains at least one element e such that o.equals(e).

Parameters

o:Object: object to be checked for containment in this queue

Returns:boolean

true if this queue contains the specified element

ensureNonEmpty	back to summary
private static Object[] ensureNonEmpty(Object[] es) Ensures that queue[0] exists, helping peek() and poll().

forEach back to summary

forEach	back to summary
public void forEach(Consumer<? super E> action) Overrides default java.lang.Iterable.forEach. Doc from java.lang.Iterable.forEach. Performs the given action for each element of the `Iterable` until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller. The behavior of this method is unspecified if the action performs side-effects that modify the underlying source of elements, unless an overriding class has specified a concurrent modification policy. Parameters action:Consumer<? super E> The action to be performed for each element Exceptions NullPointerException: if the specified action is null

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

Overrides default java.lang.Iterable.forEach.

Doc from java.lang.Iterable.forEach.

Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller.

The behavior of this method is unspecified if the action performs side-effects that modify the underlying source of elements, unless an overriding class has specified a concurrent modification policy.

Parameters

action:Consumer<? super E>: The action to be performed for each element

Exceptions

NullPointerException:: if the specified action is null

grow	back to summary
private void grow(int minCapacity) Increases the capacity of the array. Parameters minCapacity:int the desired minimum capacity

grow

back to summary

private void grow(int minCapacity)

Increases the capacity of the array.

Parameters

minCapacity:int: the desired minimum capacity

heapify	back to summary
private void heapify() Establishes the heap invariant (described above) in the entire tree, assuming nothing about the order of the elements prior to the call. This classic algorithm due to Floyd (1964) is known to be O(size).

indexOf	back to summary
private int indexOf(Object o)

initElementsFromCollection	back to summary
private void initElementsFromCollection(Collection<? extends E> c)

initFromCollection	back to summary
private void initFromCollection(Collection<? extends E> c) Initializes queue array with elements from the given Collection. Parameters c:Collection<? extends E> the collection

initFromCollection

back to summary

private void initFromCollection(Collection<? extends E> c)

Initializes queue array with elements from the given Collection.

Parameters

c:Collection<? extends E>: the collection

initFromPriorityQueue	back to summary
private void initFromPriorityQueue(PriorityQueue<? extends E> c)

isClear	back to summary
private static boolean isClear(long[] bits, int i)

iterator	back to summary
public Iterator<E> iterator() Implements abstract java.util.AbstractCollection.iterator. Implements java.util.Collection.iterator. Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order. Returns:Iterator<E> an iterator over the elements in this queue

iterator

back to summary

public Iterator<E> iterator()

Implements abstract java.util.AbstractCollection.iterator.

Implements java.util.Collection.iterator.

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

Returns:Iterator<E>: an iterator over the elements in this queue

nBits	back to summary
private static long[] nBits(int n)

offer back to summary

offer	back to summary
public boolean offer(E e) Implements java.util.Queue.offer. Inserts the specified element into this priority queue. Parameters e:E Doc from java.util.Queue.offer. the element to add Returns:boolean `true` (as specified by `Queue#offer`) Exceptions ClassCastException: if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering NullPointerException: if the specified element is null

public boolean offer(E e)

Implements java.util.Queue.offer.

Inserts the specified element into this priority queue.

Parameters

e:E

Doc from java.util.Queue.offer.

the element to add

Returns:boolean

true (as specified by Queue#offer)

Exceptions

ClassCastException:: if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering
NullPointerException:: if the specified element is null

peek back to summary

peek	back to summary
public E peek() Implements java.util.Queue.peek. Doc from java.util.Queue.peek. Retrieves, but does not remove, the head of this queue, or returns `null` if this queue is empty. Returns:E the head of this queue, or `null` if this queue is empty

public E peek()

Implements java.util.Queue.peek.

Doc from java.util.Queue.peek.

Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

Returns:E: the head of this queue, or null if this queue is empty

poll back to summary

poll	back to summary
public E poll() Implements java.util.Queue.poll. Doc from java.util.Queue.poll. Retrieves and removes the head of this queue, or returns `null` if this queue is empty. Returns:E the head of this queue, or `null` if this queue is empty

public E poll()

Implements java.util.Queue.poll.

Doc from java.util.Queue.poll.

Retrieves and removes the head of this queue, or returns null if this queue is empty.

Returns:E: the head of this queue, or null if this queue is empty

readObject back to summary

readObject	back to summary
private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException Reconstitutes the `PriorityQueue` instance from a stream (that is, deserializes it). Parameters s:ObjectInputStream the stream Annotations @Serial Exceptions IOException: if an I/O error occurs ClassNotFoundException: if the class of a serialized object could not be found

private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException

Reconstitutes the PriorityQueue instance from a stream (that is, deserializes it).

Parameters

s:ObjectInputStream: the stream

Annotations

@Serial

Exceptions

IOException:: if an I/O error occurs
ClassNotFoundException:: if the class of a serialized object could not be found

remove back to summary

remove	back to summary
public boolean remove(Object o) Overrides java.util.AbstractCollection.remove. Implements java.util.Collection.remove. Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element `e` such that `o.equals(e)`, if this queue contains one or more such elements. Returns `true` if and only if this queue contained the specified element (or equivalently, if this queue changed as a result of the call). Parameters o:Object element to be removed from this queue, if present Returns:boolean `true` if this queue changed as a result of the call

public boolean remove(Object o)

Overrides java.util.AbstractCollection.remove.

Implements java.util.Collection.remove.

Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element e such that o.equals(e), if this queue contains one or more such elements. Returns true if and only if this queue contained the specified element (or equivalently, if this queue changed as a result of the call).

Parameters

o:Object: element to be removed from this queue, if present

Returns:boolean

true if this queue changed as a result of the call

removeAll back to summary

removeAll	back to summary
public boolean removeAll(Collection<?> c) Overrides java.util.AbstractCollection.removeAll. Implements java.util.Collection.removeAll. Doc from java.util.Collection.removeAll. Removes all of this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection. Parameters c:Collection<?> collection containing elements to be removed from this collection Returns:boolean `true` if this collection changed as a result of the call Exceptions NullPointerException: if this collection contains one or more null elements and the specified collection does not support null elements (optional) or if the specified collection is null

public boolean removeAll(Collection<?> c)

Overrides java.util.AbstractCollection.removeAll.

Implements java.util.Collection.removeAll.

Doc from java.util.Collection.removeAll.

Removes all of this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection.

Parameters

c:Collection<?>: collection containing elements to be removed from this collection

Returns:boolean

true if this collection changed as a result of the call

Exceptions

NullPointerException:: if this collection contains one or more null elements and the specified collection does not support null elements (optional) or if the specified collection is null

removeAt	back to summary
pack-priv E removeAt(int i) Removes the ith element from queue. Normally this method leaves the elements at up to i-1, inclusive, untouched. Under these circumstances, it returns null. Occasionally, in order to maintain the heap invariant, it must swap a later element of the list with one earlier than i. Under these circumstances, this method returns the element that was previously at the end of the list and is now at some position before i. This fact is used by iterator.remove so as to avoid missing traversing elements.

removeAt

back to summary

pack-priv E removeAt(int i)

Removes the ith element from queue. Normally this method leaves the elements at up to i-1, inclusive, untouched. Under these circumstances, it returns null. Occasionally, in order to maintain the heap invariant, it must swap a later element of the list with one earlier than i. Under these circumstances, this method returns the element that was previously at the end of the list and is now at some position before i. This fact is used by iterator.remove so as to avoid missing traversing elements.

removeEq	back to summary
pack-priv void removeEq(Object o) Identity-based version for use in Itr.remove. Parameters o:Object element to be removed from this queue, if present

removeEq

back to summary

pack-priv void removeEq(Object o)

Identity-based version for use in Itr.remove.

Parameters

o:Object: element to be removed from this queue, if present

removeIf back to summary

removeIf	back to summary
public boolean removeIf(Predicate<? super E> filter) Overrides default java.util.Collection.removeIf. Doc from java.util.Collection.removeIf. Removes all of the elements of this collection that satisfy the given predicate (optional operation). Errors or runtime exceptions thrown during iteration or by the predicate are relayed to the caller. Parameters filter:Predicate<? super E> a predicate which returns `true` for elements to be removed Returns:boolean `true` if any elements were removed Exceptions NullPointerException: if the specified filter is null

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

Overrides default java.util.Collection.removeIf.

Doc from java.util.Collection.removeIf.

Removes all of the elements of this collection that satisfy the given predicate (optional operation). Errors or runtime exceptions thrown during iteration or by the predicate are relayed to the caller.

Parameters

filter:Predicate<? super E>: a predicate which returns true for elements to be removed

Returns:boolean

true if any elements were removed

Exceptions

NullPointerException:: if the specified filter is null

retainAll back to summary

retainAll	back to summary
public boolean retainAll(Collection<?> c) Overrides java.util.AbstractCollection.retainAll. Implements java.util.Collection.retainAll. Doc from java.util.Collection.retainAll. Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection. Parameters c:Collection<?> collection containing elements to be retained in this collection Returns:boolean `true` if this collection changed as a result of the call Exceptions NullPointerException: if this collection contains one or more null elements and the specified collection does not permit null elements (optional) or if the specified collection is null

public boolean retainAll(Collection<?> c)

Overrides java.util.AbstractCollection.retainAll.

Implements java.util.Collection.retainAll.

Doc from java.util.Collection.retainAll.

Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection.

Parameters

c:Collection<?>: collection containing elements to be retained in this collection

Returns:boolean

true if this collection changed as a result of the call

Exceptions

NullPointerException:: if this collection contains one or more null elements and the specified collection does not permit null elements (optional) or if the specified collection is null

setBit	back to summary
private static void setBit(long[] bits, int i)

siftDown	back to summary
private void siftDown(int k, E x) Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf. Parameters k:int the position to fill x:E the item to insert

siftDown

back to summary

private void siftDown(int k, E x)

Inserts item x at position k, maintaining heap invariant by demoting x down the tree repeatedly until it is less than or equal to its children or is a leaf.

Parameters

k:int: the position to fill
x:E: the item to insert

siftDownComparable	back to summary
private static <T> void siftDownComparable(int k, T x, Object[] es, int n)

siftDownUsingComparator	back to summary
private static <T> void siftDownUsingComparator(int k, T x, Object[] es, int n, Comparator<? super T> cmp)

siftUp	back to summary
private void siftUp(int k, E x) Inserts item x at position k, maintaining heap invariant by promoting x up the tree until it is greater than or equal to its parent, or is the root. To simplify and speed up coercions and comparisons, the Comparable and Comparator versions are separated into different methods that are otherwise identical. (Similarly for siftDown.) Parameters k:int the position to fill x:E the item to insert

siftUp

back to summary

private void siftUp(int k, E x)

Inserts item x at position k, maintaining heap invariant by promoting x up the tree until it is greater than or equal to its parent, or is the root. To simplify and speed up coercions and comparisons, the Comparable and Comparator versions are separated into different methods that are otherwise identical. (Similarly for siftDown.)

Parameters

k:int: the position to fill
x:E: the item to insert

siftUpComparable	back to summary
private static <T> void siftUpComparable(int k, T x, Object[] es)

siftUpUsingComparator	back to summary
private static <T> void siftUpUsingComparator(int k, T x, Object[] es, Comparator<? super T> cmp)

size back to summary

public int size()

Implements abstract java.util.AbstractCollection.size.

Implements java.util.Collection.size.

Doc from java.util.Collection.size.

Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Returns:int: the number of elements in this collection

spliterator back to summary

public final Spliterator<E> spliterator()

Overrides default java.util.Collection.spliterator.

Creates a late-binding and fail-fast Spliterator over the elements in this queue. The spliterator does not traverse elements in any particular order (the ORDERED characteristic is not reported).

The Spliterator reports Spliterator#SIZED, Spliterator#SUBSIZED, and Spliterator#NONNULL. Overriding implementations should document the reporting of additional characteristic values.

Returns:Spliterator<E>: a Spliterator over the elements in this queue
Since: 1.8

toArray

back to summary

public Object[] toArray()

Overrides java.util.AbstractCollection.toArray.

Implements java.util.Collection.toArray.

Returns an array containing all of the elements in this queue. The elements are in no particular order.

The returned array will be "safe" in that no references to it are maintained by this queue. (In other words, this method must allocate a new array). The caller is thus free to modify the returned array.

This method acts as bridge between array-based and collection-based APIs.

Returns:Object[]: an array containing all of the elements in this queue

toArray back to summary

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

Overrides java.util.AbstractCollection.toArray.

Implements java.util.Collection.toArray.

Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array. The returned array elements are in no particular order. If the queue fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this queue.

If the queue fits in the specified array with room to spare (i.e., the array has more elements than the queue), the element in the array immediately following the end of the collection is set to null.

Like the toArray() method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the runtime type of the output array, and may, under certain circumstances, be used to save allocation costs.

Suppose x is a queue known to contain only strings. The following code can be used to dump the queue into a newly allocated array of String:

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

Note that toArray(new Object[0]) is identical in function to toArray().

Parameters

<T>: Doc from java.util.Collection.toArray. the component type of the array to contain the collection
a:T[]: the array into which the elements of the queue are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.

Returns:T[]

an array containing all of the elements in this queue

Exceptions

ArrayStoreException:: if the runtime type of the specified array is not a supertype of the runtime type of every element in this queue
NullPointerException:: if the specified array is null

writeObject back to summary

private void writeObject(ObjectOutputStream s) throws IOException

Saves this queue to a stream (that is, serializes it).

Parameters

s:ObjectOutputStream: the stream

Annotations

@Serial

Exceptions

IOException:: if an I/O error occurs

Serial data

The length of the array backing the instance is emitted (int), followed by all of its elements (each an Object) in the proper order.

java.util back to summary

private final Class PriorityQueue.Itr

Class Inheritance

extends Object
implements Iterator<E>

java.lang.Object
java.util.PriorityQueue.Itr

All Implemented Interfaces

java.util.Iterator

Field Summary

Modifier and Type	Field and Description
private int	cursor Index (into queue array) of element to be returned by subsequent call to next.
private int	expectedModCount The modCount value that the iterator believes that the backing Queue should have.
private ArrayDeque<E>	forgetMeNot A queue of elements that were moved from the unvisited portion of the heap into the visited portion as a result of "unlucky" element removals during the iteration.
private int	lastRet Index of element returned by most recent call to next, unless that element came from the forgetMeNot list.
private E	lastRetElt Element returned by the most recent call to next iff that element was drawn from the forgetMeNot list.

Constructor Summary

Access	Constructor and Description
pack-priv	Itr()

Method Summary

Modifier and Type	Method and Description
public boolean	hasNext() Implements java.util.Iterator.hasNext. Returns `true` if the iteration has more elements.
public E	next() Implements java.util.Iterator.next. Returns the next element in the iteration.
public void	remove() Overrides default java.util.Iterator.remove. Removes from the underlying collection the last element returned by this iterator (optional operation).

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

cursor	back to summary
private int cursor Index (into queue array) of element to be returned by subsequent call to next.

expectedModCount	back to summary
private int expectedModCount The modCount value that the iterator believes that the backing Queue should have. If this expectation is violated, the iterator has detected concurrent modification.

forgetMeNot

back to summary

private ArrayDeque<E> forgetMeNot

A queue of elements that were moved from the unvisited portion of the heap into the visited portion as a result of "unlucky" element removals during the iteration. (Unlucky element removals are those that require a siftup instead of a siftdown.) We must visit all of the elements in this list to complete the iteration. We do this after we've completed the "normal" iteration. We expect that most iterations, even those involving removals, will not need to store elements in this field.

lastRet	back to summary
private int lastRet Index of element returned by most recent call to next, unless that element came from the forgetMeNot list. Set to -1 if element is deleted by a call to remove.

lastRetElt	back to summary
private E lastRetElt Element returned by the most recent call to next iff that element was drawn from the forgetMeNot list.

Constructor Detail

Itr	back to summary
pack-priv Itr()

Method Detail

hasNext back to summary

public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

Returns:boolean: true if the iteration has more elements

back to summary

public E next()

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

Returns:E: the next element in the iteration

remove back to summary

public void remove()

Overrides default java.util.Iterator.remove.

Doc from java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next.

The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method, unless an overriding class has specified a concurrent modification policy.

The behavior of an iterator is unspecified if this method is called after a call to the forEachRemaining method.

java.util back to summary

pack-priv final Class PriorityQueue.PriorityQueueSpliterator

Class Inheritance

extends Object
implements Spliterator<E>

java.lang.Object
java.util.PriorityQueue.PriorityQueueSpliterator

All Implemented Interfaces

java.util.Spliterator

Field Summary

Modifier and Type	Field and Description
private int	expectedModCount
private int	fence
private int	index

Constructor Summary

Access	Constructor and Description
pack-priv	PriorityQueueSpliterator(int origin, int fence, int expectedModCount) Creates new spliterator covering the given range.

Method Summary

Modifier and Type	Method and Description
public int	characteristics() Implements java.util.Spliterator.characteristics. Returns a set of characteristics of this Spliterator and its elements.
public long	estimateSize() Implements java.util.Spliterator.estimateSize. Returns an estimate of the number of elements that would be encountered by a `forEachRemaining` traversal, or returns `Long#MAX_VALUE` if infinite, unknown, or too expensive to compute.
public void	forEachRemaining(Consumer<? super E> The action action) Overrides default java.util.Spliterator.forEachRemaining. Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception.
private int	getFence()
public boolean	tryAdvance(Consumer<? super E> The action whose operation is performed at-most once action) Implements java.util.Spliterator.tryAdvance. If a remaining element exists: performs the given action on it, returning `true`; else returns `false`.
public PriorityQueue<E>.PriorityQueueSpliterator	trySplit() Implements java.util.Spliterator.trySplit. If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

expectedModCount	back to summary
private int expectedModCount

fence	back to summary
private int fence

index	back to summary
private int index

Constructor Detail

PriorityQueueSpliterator	back to summary
pack-priv PriorityQueueSpliterator(int origin, int fence, int expectedModCount) Creates new spliterator covering the given range.

Method Detail

characteristics back to summary

public int characteristics()

Implements java.util.Spliterator.characteristics.

Doc from java.util.Spliterator.characteristics.

Returns a set of characteristics of this Spliterator and its elements. The result is represented as ORed values from ORDERED, DISTINCT, SORTED, SIZED, NONNULL, IMMUTABLE, CONCURRENT, SUBSIZED. Repeated calls to characteristics() on a given spliterator, prior to or in-between calls to trySplit, should always return the same result.

If a Spliterator reports an inconsistent set of characteristics (either those returned from a single invocation or across multiple invocations), no guarantees can be made about any computation using this Spliterator.

Returns:int: a representation of characteristics

estimateSize back to summary

public long estimateSize()

Implements java.util.Spliterator.estimateSize.

Doc from java.util.Spliterator.estimateSize.

Returns an estimate of the number of elements that would be encountered by a forEachRemaining traversal, or returns Long#MAX_VALUE if infinite, unknown, or too expensive to compute.

If this Spliterator is SIZED and has not yet been partially traversed or split, or this Spliterator is SUBSIZED and has not yet been partially traversed, this estimate must be an accurate count of elements that would be encountered by a complete traversal. Otherwise, this estimate may be arbitrarily inaccurate, but must decrease as specified across invocations of trySplit.

Returns:long: the estimated size, or Long.MAX_VALUE if infinite, unknown, or too expensive to compute.

forEachRemaining back to summary

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

Overrides default java.util.Spliterator.forEachRemaining.

Doc from java.util.Spliterator.forEachRemaining.

Performs the given action for each remaining element, sequentially in the current thread, until all elements have been processed or the action throws an exception. If this Spliterator is ORDERED, actions are performed in encounter order. Exceptions thrown by the action are relayed to the caller.

Subsequent behavior of a spliterator is unspecified if the action throws an exception.

Parameters

action:Consumer<? super E>: The action

getFence	back to summary
private int getFence()

tryAdvance back to summary

public boolean tryAdvance(Consumer<? super E> action)

Implements java.util.Spliterator.tryAdvance.

Doc from java.util.Spliterator.tryAdvance.

If a remaining element exists: performs the given action on it, returning true; else returns false. If this Spliterator is ORDERED the action is performed on the next element in encounter order. Exceptions thrown by the action are relayed to the caller.

Subsequent behavior of a spliterator is unspecified if the action throws an exception.

Parameters

action:Consumer<? super E>: The action whose operation is performed at-most once

Returns:boolean

false if no remaining elements existed upon entry to this method, else true.

trySplit back to summary

public PriorityQueue<E>.PriorityQueueSpliterator trySplit()

Implements java.util.Spliterator.trySplit.

Doc from java.util.Spliterator.trySplit.

If this spliterator can be partitioned, returns a Spliterator covering elements, that will, upon return from this method, not be covered by this Spliterator.

If this Spliterator is ORDERED, the returned Spliterator must cover a strict prefix of the elements.

Unless this Spliterator covers an infinite number of elements, repeated calls to trySplit() must eventually return null. Upon non-null return:

the value reported for estimateSize() before splitting, must, after splitting, be greater than or equal to estimateSize() for this and the returned Spliterator; and
if this Spliterator is SUBSIZED, then estimateSize() for this spliterator before splitting must be equal to the sum of estimateSize() for this and the returned Spliterator after splitting.

This method may return null for any reason, including emptiness, inability to split after traversal has commenced, data structure constraints, and efficiency considerations.

Returns:PriorityQueue<E>.PriorityQueueSpliterator: a Spliterator covering some portion of the elements, or null if this spliterator cannot be split

public Class PriorityQueue<E>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private final Class PriorityQueue.Itr

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv final Class PriorityQueue.PriorityQueueSpliterator

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail