Skip to content

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

Returns


Public Functions

clear

[Source]

Remove all elements from the heap.

fun ref clear()
: None val

Returns


size

[Source]

Return the number of elements in the heap.

fun box size()
: USize val

Returns


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


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 = seq,
  len: USize val = seq)
: None val

Parameters

Returns


concat

[Source]

Add len iterated elements, starting from the given offset.

fun ref concat(
  iter: Iterator[A^] ref,
  offset: USize val = seq,
  len: USize val = seq)
: None val

Parameters

Returns


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


Private Functions

_make_heap

[Source]

fun ref _make_heap()
: None val

Returns


_sift_up

[Source]

fun ref _sift_up(
  n: USize val)
: None val

Parameters

Returns


_sift_down

[Source]

fun ref _sift_down(
  start: USize val,
  n: USize val)
: Bool val

Parameters

Returns


_apply

[Source]

fun box _apply(
  i: USize val)
: this->A ?

Parameters

Returns

  • this->A ?