/Pony

# 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^
```

## Public Functions

[Source]

Remove all elements from the heap.

```fun ref clear()
: None val
```

### size

[Source]

Return the number of elements in the heap.

```fun box size()
: 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 ?
```

• 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
```

• value: A

### 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^ ?
```

• 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
```

### 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
```

### 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^
```

## Private Functions

### _make_heap

[Source]

```fun ref _make_heap()
: None val
```

### _sift_up

[Source]

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

### _sift_down

[Source]

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

### _apply

[Source]

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

#### Returns

• this->A ?

© 2016-2018, The Pony Developers
© 2014-2015, Causality Ltd.
Licensed under the BSD 2-Clause License.
https://stdlib.ponylang.io/collections-BinaryHeap