Skip to content
Buy me a coffee

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

E

new PriorityQueue<E>(): PriorityQueue<E>

Defined in: src/queue/PriorityQueue.ts:155

Creates an empty queue with natural ordering.

PriorityQueue<E>

AbstractQueue.constructor

new PriorityQueue<E>(comparator): PriorityQueue<E>

Defined in: src/queue/PriorityQueue.ts:160

Creates an empty queue ordered by comparator.

Comparator<E> | null

the ordering; null (or undefined) means natural ordering

PriorityQueue<E>

AbstractQueue<E>.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.

number

expected number of elements

Comparator<E> | null

the ordering; null or omitted means natural ordering

PriorityQueue<E>

IllegalArgumentException if initialCapacity < 1

AbstractQueue<E>.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.

Collection<E>

PriorityQueue<E>

NullPointerException if c holds null or undefined

ClassCastException if the elements cannot be compared by natural ordering

AbstractQueue<E>.constructor

[INSPECT](): string

Defined in: src/abstract/AbstractCollection.ts:195

Node’s util.inspect hook: console.log prints the toString() form.

string

AbstractQueue.[INSPECT]


[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.

IterableIterator<E>

AbstractQueue.[iterator]


add(e): boolean

Defined in: src/abstract/AbstractQueue.ts:28

Inserts e via offer; returns true.

E

boolean

IllegalStateException if offer returns false (the queue is full)

AbstractQueue.add


addAll(c): boolean

Defined in: src/abstract/AbstractQueue.ts:68

Calls add for each element of c; returns true if the queue changed.

Collection<E>

boolean

NullPointerException if c is null

IllegalArgumentException if c is this queue

IllegalStateException if the queue fills up part-way (earlier elements stay added)

AbstractQueue.addAll


clear(): void

Defined in: src/queue/PriorityQueue.ts:372

Removes all elements. The comparator is kept.

void

AbstractQueue.clear


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.

Comparator<E> | null


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.

unknown

boolean

AbstractQueue.contains


containsAll(c): boolean

Defined in: src/abstract/AbstractCollection.ts:83

Returns true if this collection contains every element of c (calls contains for each).

Collection<unknown>

boolean

NullPointerException if c is null

AbstractQueue.containsAll


element(): E

Defined in: src/abstract/AbstractQueue.ts:51

Returns the head without removing it, via peek.

E

NoSuchElementException if the queue is empty

AbstractQueue.element


equals(o): boolean

Defined in: src/abstract/AbstractCollection.ts:185

Identity by default; List/Set/Map subclasses override with value equality.

unknown

boolean

AbstractQueue.equals


forEach(action): void

Defined in: src/queue/PriorityQueue.ts:424

Calls action for each element, in heap order (not sorted order).

(e) => void

void

NullPointerException if action is null

ConcurrentModificationException if action structurally modifies this queue

AbstractQueue.forEach


hashCode(): number

Defined in: src/abstract/AbstractCollection.ts:190

Identity hash by default, consistent with the identity equals.

number

AbstractQueue.hashCode


isEmpty(): boolean

Defined in: src/abstract/AbstractCollection.ts:29

Returns size() === 0.

boolean

AbstractQueue.isEmpty


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.

Iterator<E>

AbstractQueue.iterator


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.

E

boolean

always true (the queue is unbounded)

NullPointerException if e is null or undefined

ClassCastException if e cannot be compared with the elements by natural ordering

AbstractQueue.offer


parallelStream(): Stream<E>

Defined in: src/abstract/AbstractCollection.ts:180

Returns a stream over spliterator() flagged as parallel.

Stream<E>

AbstractQueue.parallelStream


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.

E | null

AbstractQueue.peek


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.

E | null

AbstractQueue.poll


remove(): E

Defined in: src/queue/PriorityQueue.ts:306

Removes and returns the head (the least element), in O(log n).

E

NoSuchElementException if this queue is empty

AbstractQueue.remove

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.

unknown

boolean

true if an element was removed

AbstractQueue.remove


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.

Collection<unknown>

boolean

NullPointerException if c is null

AbstractQueue.removeAll


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.

(e) => boolean

boolean

true if any element was removed

NullPointerException if filter is null

ConcurrentModificationException if filter structurally modifies this queue

AbstractQueue.removeIf


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.

Collection<unknown>

boolean

NullPointerException if c is null

AbstractQueue.retainAll


size(): number

Defined in: src/queue/PriorityQueue.ts:216

Returns the number of elements. O(1).

number

AbstractQueue.size


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.

Spliterator<E>

AbstractQueue.spliterator


stream(): Stream<E>

Defined in: src/abstract/AbstractCollection.ts:175

Returns a sequential stream over spliterator().

Stream<E>

AbstractQueue.stream


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

E[]

AbstractQueue.toArray

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

A extends WritableArrayLike<E>

(length) => A

creates the target array for a given length

A

AbstractQueue.toArray


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

string

AbstractQueue.toString


static of<E>(…xs): PriorityQueue<E>

Defined in: src/queue/PriorityQueue.ts:202

Creates a queue with natural ordering holding xs, heapified in O(n).

E

…E[]

PriorityQueue<E>

NullPointerException if any argument is null or undefined

ClassCastException if the arguments cannot be compared by natural ordering