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^
Remove all elements from the heap.
fun ref clear() : None val
Return the number of elements in the heap.
fun box size() : 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 ?
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
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^ ?
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
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
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^
fun ref _make_heap() : None val
fun ref _sift_up( n: USize val) : None val
fun ref _sift_down( start: USize val, n: USize val) : Bool val
fun box _apply( i: USize val) : this->A ?
© 2016-2018, The Pony Developers
© 2014-2015, Causality Ltd.
Licensed under the BSD 2-Clause License.
https://stdlib.ponylang.io/collections-BinaryHeap