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 toUnorderedList operation copies, but does not sort, the elements, and is linear, O(n).
  • The toSet operation effectively adds each element to the new set, taking an expected O(n*log(n)) time.
Implemented types

Constructors

HeapPriorityQueue.new([int comparison(E, E)?])
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.
no setteroverride
hashCode → int
The hash code for this object.
no setterinherited
isEmpty → bool
Whether the queue is empty.
no setteroverride
isNotEmpty → bool
Whether the queue has any elements.
no setteroverride
length → int
Number of elements in the queue.
no setteroverride
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited
unorderedElements → Iterable<E>
Provides efficient access to all the elements currently in the queue.
no setteroverride

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
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
remove(E element) → bool
Removes an element of the queue that compares equal to element.
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
toUnorderedList() → List<E>
Returns a list of the elements of this queue in no specific order.
override

Operators

operator ==(Object other) → bool
The equality operator.
inherited