PriorityQueue
Defined in: src/queue/PriorityQueue.ts:145
Unbounded priority queue on an array-backed binary min-heap. The head is the least element by the
comparator, or by natural ordering when there is none (numbers numerically, strings by UTF-16 code
unit, objects through compareTo(); anything else throws ClassCastException).
offer/add and poll/remove() are O(log n), peek is O(1), contains and remove(o) are
O(n), and building from a collection or of heapifies in O(n). Rejects null and undefined with
NullPointerException, so a null from poll() or peek() always means empty.
Iteration, forEach, toArray(), toString() and streams follow heap order, not sorted order:
only the first element is guaranteed to be the least. poll() the elements out to get them in
priority order. Ties are broken arbitrarily (the heap is not stable).
Extends
Section titled “Extends”Type Parameters
Section titled “Type Parameters”E
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new PriorityQueue<
E>():PriorityQueue<E>
Defined in: src/queue/PriorityQueue.ts:155
Creates an empty queue with natural ordering.
Returns
Section titled “Returns”PriorityQueue<E>
Overrides
Section titled “Overrides”Constructor
Section titled “Constructor”new PriorityQueue<
E>(comparator):PriorityQueue<E>
Defined in: src/queue/PriorityQueue.ts:160
Creates an empty queue ordered by comparator.
Parameters
Section titled “Parameters”comparator
Section titled “comparator”Comparator<E> | null
the ordering; null (or undefined) means natural ordering
Returns
Section titled “Returns”PriorityQueue<E>
Overrides
Section titled “Overrides”AbstractQueue<E>.constructor
Constructor
Section titled “Constructor”new PriorityQueue<
E>(initialCapacity,comparator?):PriorityQueue<E>
Defined in: src/queue/PriorityQueue.ts:168
Creates an empty queue ordered by comparator. initialCapacity is validated but only a hint:
the queue grows as needed.
Parameters
Section titled “Parameters”initialCapacity
Section titled “initialCapacity”number
expected number of elements
comparator?
Section titled “comparator?”Comparator<E> | null
the ordering; null or omitted means natural ordering
Returns
Section titled “Returns”PriorityQueue<E>
Throws
Section titled “Throws”IllegalArgumentException if initialCapacity < 1
Overrides
Section titled “Overrides”AbstractQueue<E>.constructor
Constructor
Section titled “Constructor”new PriorityQueue<
E>(c):PriorityQueue<E>
Defined in: src/queue/PriorityQueue.ts:175
Creates a queue holding the elements of c, heapified bottom-up in O(n). The comparator is
taken from c when it has one: a PriorityQueue, or a sorted collection such as a TreeSet.
Parameters
Section titled “Parameters”Collection<E>
Returns
Section titled “Returns”PriorityQueue<E>
Throws
Section titled “Throws”NullPointerException if c holds null or undefined
Throws
Section titled “Throws”ClassCastException if the elements cannot be compared by natural ordering
Overrides
Section titled “Overrides”AbstractQueue<E>.constructor
Methods
Section titled “Methods”[INSPECT]()
Section titled “[INSPECT]()”[INSPECT]():
string
Defined in: src/abstract/AbstractCollection.ts:195
Node’s util.inspect hook: console.log prints the toString() form.
Returns
Section titled “Returns”string
Inherited from
Section titled “Inherited from”[iterator]()
Section titled “[iterator]()”[iterator]():
IterableIterator<E>
Defined in: src/queue/PriorityQueue.ts:446
Returns a JS iterator over the elements in heap order, not sorted order, for for...of and spread; fail-fast.
Returns
Section titled “Returns”IterableIterator<E>
Overrides
Section titled “Overrides”add(
e):boolean
Defined in: src/abstract/AbstractQueue.ts:28
Inserts e via offer; returns true.
Parameters
Section titled “Parameters”E
Returns
Section titled “Returns”boolean
Throws
Section titled “Throws”IllegalStateException if offer returns false (the queue is full)
Inherited from
Section titled “Inherited from”addAll()
Section titled “addAll()”addAll(
c):boolean
Defined in: src/abstract/AbstractQueue.ts:68
Calls add for each element of c; returns true if the queue changed.
Parameters
Section titled “Parameters”Collection<E>
Returns
Section titled “Returns”boolean
Throws
Section titled “Throws”NullPointerException if c is null
Throws
Section titled “Throws”IllegalArgumentException if c is this queue
Throws
Section titled “Throws”IllegalStateException if the queue fills up part-way (earlier elements stay added)
Inherited from
Section titled “Inherited from”clear()
Section titled “clear()”clear():
void
Defined in: src/queue/PriorityQueue.ts:372
Removes all elements. The comparator is kept.
Returns
Section titled “Returns”void
Overrides
Section titled “Overrides”comparator()
Section titled “comparator()”comparator():
Comparator<E> |null
Defined in: src/queue/PriorityQueue.ts:211
Returns the comparator that orders this queue, or null if it uses natural ordering.
Returns
Section titled “Returns”Comparator<E> | null
contains()
Section titled “contains()”contains(
o):boolean
Defined in: src/queue/PriorityQueue.ts:322
Returns true if this queue contains an element equal to o (by Objects.equals). O(n) linear search; false for null or undefined.
Parameters
Section titled “Parameters”unknown
Returns
Section titled “Returns”boolean
Overrides
Section titled “Overrides”containsAll()
Section titled “containsAll()”containsAll(
c):boolean
Defined in: src/abstract/AbstractCollection.ts:83
Returns true if this collection contains every element of c (calls contains for each).
Parameters
Section titled “Parameters”Collection<unknown>
Returns
Section titled “Returns”boolean
Throws
Section titled “Throws”NullPointerException if c is null
Inherited from
Section titled “Inherited from”element()
Section titled “element()”element():
E
Defined in: src/abstract/AbstractQueue.ts:51
Returns the head without removing it, via peek.
Returns
Section titled “Returns”E
Throws
Section titled “Throws”NoSuchElementException if the queue is empty
Inherited from
Section titled “Inherited from”equals()
Section titled “equals()”equals(
o):boolean
Defined in: src/abstract/AbstractCollection.ts:185
Identity by default; List/Set/Map subclasses override with value equality.
Parameters
Section titled “Parameters”unknown
Returns
Section titled “Returns”boolean
Inherited from
Section titled “Inherited from”forEach()
Section titled “forEach()”forEach(
action):void
Defined in: src/queue/PriorityQueue.ts:424
Calls action for each element, in heap order (not sorted order).
Parameters
Section titled “Parameters”action
Section titled “action”(e) => void
Returns
Section titled “Returns”void
Throws
Section titled “Throws”NullPointerException if action is null
Throws
Section titled “Throws”ConcurrentModificationException if action structurally modifies this queue
Overrides
Section titled “Overrides”hashCode()
Section titled “hashCode()”hashCode():
number
Defined in: src/abstract/AbstractCollection.ts:190
Identity hash by default, consistent with the identity equals.
Returns
Section titled “Returns”number
Inherited from
Section titled “Inherited from”isEmpty()
Section titled “isEmpty()”isEmpty():
boolean
Defined in: src/abstract/AbstractCollection.ts:29
Returns size() === 0.
Returns
Section titled “Returns”boolean
Inherited from
Section titled “Inherited from”iterator()
Section titled “iterator()”iterator():
Iterator<E>
Defined in: src/queue/PriorityQueue.ts:435
Returns a fail-fast iterator over the elements in heap order, not sorted order. Supports remove.
Returns
Section titled “Returns”Iterator<E>
Overrides
Section titled “Overrides”offer()
Section titled “offer()”offer(
e):boolean
Defined in: src/queue/PriorityQueue.ts:227
Inserts e into this queue and sifts it up, in O(log n). If a comparison throws, the queue is left
unchanged.
Parameters
Section titled “Parameters”E
Returns
Section titled “Returns”boolean
always true (the queue is unbounded)
Throws
Section titled “Throws”NullPointerException if e is null or undefined
Throws
Section titled “Throws”ClassCastException if e cannot be compared with the elements by natural ordering
Overrides
Section titled “Overrides”parallelStream()
Section titled “parallelStream()”parallelStream():
Stream<E>
Defined in: src/abstract/AbstractCollection.ts:180
Returns a stream over spliterator() flagged as parallel.
Returns
Section titled “Returns”Stream<E>
Inherited from
Section titled “Inherited from”peek()
Section titled “peek()”peek():
E|null
Defined in: src/queue/PriorityQueue.ts:297
Returns the head (the least element) without removing it, in O(1), or null if this queue is empty.
Returns
Section titled “Returns”E | null
Overrides
Section titled “Overrides”poll()
Section titled “poll()”poll():
E|null
Defined in: src/queue/PriorityQueue.ts:280
Removes and returns the head (the least element) in O(log n), or null if this queue is empty.
Returns
Section titled “Returns”E | null
Overrides
Section titled “Overrides”remove()
Section titled “remove()”Call Signature
Section titled “Call Signature”remove():
E
Defined in: src/queue/PriorityQueue.ts:306
Removes and returns the head (the least element), in O(log n).
Returns
Section titled “Returns”E
Throws
Section titled “Throws”NoSuchElementException if this queue is empty
Overrides
Section titled “Overrides”Call Signature
Section titled “Call Signature”remove(
o):boolean
Defined in: src/queue/PriorityQueue.ts:312
Removes one element equal to o (by Objects.equals), if present: an O(n) search, then an
O(log n) heap repair.
Parameters
Section titled “Parameters”unknown
Returns
Section titled “Returns”boolean
true if an element was removed
Overrides
Section titled “Overrides”removeAll()
Section titled “removeAll()”removeAll(
c):boolean
Defined in: src/abstract/AbstractCollection.ts:108
Removes every element that c contains, through the iterator’s remove(); returns true if any was removed.
Parameters
Section titled “Parameters”Collection<unknown>
Returns
Section titled “Returns”boolean
Throws
Section titled “Throws”NullPointerException if c is null
Inherited from
Section titled “Inherited from”removeIf()
Section titled “removeIf()”removeIf(
filter):boolean
Defined in: src/queue/PriorityQueue.ts:397
Removes every element for which filter returns true. O(n): filters, then re-heapifies. Every
element is tested before anything is removed, so a throwing predicate, or one that modifies the queue,
leaves the queue unchanged.
Parameters
Section titled “Parameters”filter
Section titled “filter”(e) => boolean
Returns
Section titled “Returns”boolean
true if any element was removed
Throws
Section titled “Throws”NullPointerException if filter is null
Throws
Section titled “Throws”ConcurrentModificationException if filter structurally modifies this queue
Overrides
Section titled “Overrides”retainAll()
Section titled “retainAll()”retainAll(
c):boolean
Defined in: src/abstract/AbstractCollection.ts:118
Removes every element that c does not contain, through the iterator’s remove(); returns true if any was
removed.
Parameters
Section titled “Parameters”Collection<unknown>
Returns
Section titled “Returns”boolean
Throws
Section titled “Throws”NullPointerException if c is null
Inherited from
Section titled “Inherited from”size()
Section titled “size()”size():
number
Defined in: src/queue/PriorityQueue.ts:216
Returns the number of elements. O(1).
Returns
Section titled “Returns”number
Overrides
Section titled “Overrides”spliterator()
Section titled “spliterator()”spliterator():
Spliterator<E>
Defined in: src/queue/PriorityQueue.ts:440
Returns a spliterator over the elements, used to build streams: SIZED | SUBSIZED | NONNULL in heap order (not ORDERED), late-binding, fail-fast, splits in halves.
Returns
Section titled “Returns”Spliterator<E>
Overrides
Section titled “Overrides”stream()
Section titled “stream()”stream():
Stream<E>
Defined in: src/abstract/AbstractCollection.ts:175
Returns a sequential stream over spliterator().
Returns
Section titled “Returns”Stream<E>
Inherited from
Section titled “Inherited from”toArray()
Section titled “toArray()”Call Signature
Section titled “Call Signature”toArray():
E[]
Defined in: src/queue/PriorityQueue.ts:379
Returns a new array with all elements in heap order, not sorted order. Changing the array does not affect this queue. O(n).
Returns
Section titled “Returns”E[]
Overrides
Section titled “Overrides”Call Signature
Section titled “Call Signature”toArray<
A>(generator):A
Defined in: src/queue/PriorityQueue.ts:384
Fills an array created by generator(size()) with the elements in heap order, and returns it. O(n).
Type Parameters
Section titled “Type Parameters”A extends WritableArrayLike<E>
Parameters
Section titled “Parameters”generator
Section titled “generator”(length) => A
creates the target array for a given length
Returns
Section titled “Returns”A
Overrides
Section titled “Overrides”toString()
Section titled “toString()”toString():
string
Defined in: src/abstract/AbstractCollection.ts:199
Returns [e1, e2, ...] in iteration order; an element that is this collection prints as (this Collection).
Returns
Section titled “Returns”string
Inherited from
Section titled “Inherited from”
staticof<E>(…xs):PriorityQueue<E>
Defined in: src/queue/PriorityQueue.ts:202
Creates a queue with natural ordering holding xs, heapified in O(n).
Type Parameters
Section titled “Type Parameters”E
Parameters
Section titled “Parameters”…E[]
Returns
Section titled “Returns”PriorityQueue<E>
Throws
Section titled “Throws”NullPointerException if any argument is null or undefined
Throws
Section titled “Throws”ClassCastException if the arguments cannot be compared by natural ordering