BinaryHeap[A: Comparable[A] #read, P: (_BinaryHeapPriority[A] val & (MinHeapPriority[A] val | MaxHeapPriority[A] val))]¶

[Source]

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¶

[Source]

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¶

[Source]

Remove all elements from the heap.

fun ref clear()
: None val

Returns¶

None val

size¶

[Source]

Return the number of elements in the heap.

fun box size()
: USize val

Returns¶

USize val

peek¶

[Source]

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¶

[Source]

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¶

[Source]

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¶

[Source]

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¶

[Source]

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¶

iter: Iterator[A^] ref
offset: USize val = 0
len: USize val = call

Returns¶

None val

values¶

[Source]

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^