collections BinaryHeap - tadashi9e/gmp4pony GitHub Wiki
BinaryHeap[A: Comparable[A] #read, P: (_BinaryHeapPriority[A] val & (MinHeapPriority[A] val | MaxHeapPriority[A] val))]
A priority queue implemented as a binary heap. The BinaryHeapPriority type
parameter determines whether this is max-heap or a min-heap.
class ref BinaryHeap[A: Comparable[A] #read, P: (_BinaryHeapPriority[A] val & (MinHeapPriority[A] val | MaxHeapPriority[A] val))]Create an empty heap with space for len elements.
new ref create(
len: USize val)
: BinaryHeap[A, P] ref^- len: USize val
- BinaryHeap[A, P] ref^
Remove all elements from the heap.
fun ref clear()
: None val- None val
Return the number of elements in the heap.
fun box size()
: USize val- USize val
Return the highest priority item in the heap. For max-heaps, the greatest item will be returned. For min-heaps, the smallest item will be returned.
fun box peek()
: this->A ?- this->A ?
Push an item into the heap.
The time complexity of this operation is O(log(n)) with respect to the size of the heap.
fun ref push(
value: A)
: None val- value: A
- None val
Remove the highest priority value from the heap and return it. For max-heaps, the greatest item will be returned. For min-heaps, the smallest item will be returned.
The time complexity of this operation is O(log(n)) with respect to the size of the heap.
fun ref pop()
: A^ ?- A^ ?
Append len elements from a sequence, starting from the given offset.
fun ref append(
seq: (ReadSeq[A] box & ReadElement[A^] box),
offset: USize val = 0,
len: USize val = call)
: None val- seq: (ReadSeq[A] box & ReadElement[A^] box)
- offset: USize val = 0
- len: USize val = call
- None val
Add len iterated elements, starting from the given offset.
fun ref concat(
iter: Iterator[A^] ref,
offset: USize val = 0,
len: USize val = call)
: None val- None val
Return an iterator for the elements in the heap. The order of elements is arbitrary.
fun box values()
: ArrayValues[A, this->Array[A] ref] ref^- ArrayValues[A, this->Array[A] ref] ref^