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))]
Constructors¶
create¶
Create an empty heap with space for len elements.
new ref create(
len: USize val)
: BinaryHeap[A, P] ref^
Parameters¶
- len: USize val
Returns¶
- BinaryHeap[A, P] ref^
Public Functions¶
clear¶
Remove all elements from the heap.
fun ref clear()
: None val
Returns¶
- None val
size¶
Return the number of elements in the heap.
fun box size()
: USize val
Returns¶
- USize val
peek¶
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 ?
Returns¶
- this->A ?
push¶
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
Parameters¶
- value: A
Returns¶
- None val
pop¶
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^ ?
Returns¶
- A^ ?
append¶
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
Parameters¶
- seq: (ReadSeq[A] box & ReadElement[A^] box)
- offset: USize val = 0
- len: USize val = call
Returns¶
- None val
concat¶
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
Parameters¶
Returns¶
- None val
values¶
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^
Returns¶
- ArrayValues[A, this->Array[A] ref] ref^