HeapPriorityQueue<E> class

Heap based priority queue.

The elements are kept in a heap structure, where the element with the highest priority is immediately accessible, and modifying a single element takes logarithmic time in the number of elements on average.

  • The add and removeFirst operations take amortized logarithmic time, O(log(n)), but may occasionally take linear time when growing the capacity of the heap.
  • The addAll operation works as doing repeated add operations.
  • The first getter takes constant time, O(1).
  • The clear and removeAll methods also take constant time, O(1).
  • The contains and remove operations may need to search the entire queue for the elements, taking O(n) time.
  • The toList operation effectively sorts the elements, taking O(n*log(n)) time.
  • The toSet operation effectively adds each element to the new set, taking an expected O(n*log(n)) time.
Implemented types

Constructors

HeapPriorityQueue([int comparison(E e1, E e2) ])
Create a new priority queue. [...]

Properties

comparison → Comparator<E>
The comparison being used to compare the priority of elements.
final
first → E
Returns the next element that will be returned by removeFirst. [...]
read-only, override
isEmpty → bool
Whether the queue is empty.
read-only, override
isNotEmpty → bool
Whether the queue has any elements.
read-only, override
length → int
Number of elements in the queue.
read-only, override
hashCode → int
The hash code for this object. [...]
read-only, inherited
runtimeType → Type
A representation of the runtime type of the object.
read-only, inherited

Methods

add(E element) → void
Adds element to the queue. [...]
override
addAll(Iterable<E> elements) → void
Adds all elements to the queue.
override
clear() → void
Removes all the elements from this queue.
override
contains(E object) → bool
Checks if object is in the queue. [...]
override
remove(E element) → bool
Removes an element that compares equal to element in the queue. [...]
override
removeAll() → Iterable<E>
Removes all the elements from this queue and returns them. [...]
override
removeFirst() → E
Removes and returns the element with the highest priority. [...]
override
toList() → List<E>
Returns a list of the elements of this queue in priority order. [...]
override
toSet() → Set<E>
Return a comparator based set using the comparator of this queue. [...]
override
toString() → String
Returns some representation of the queue. [...]
override
noSuchMethod(Invocation invocation) → dynamic
Invoked when a non-existent method or property is accessed. [...]
inherited

Operators

operator ==(dynamic other) → bool
The equality operator. [...]
inherited