BinaryHeap

struct BinaryHeap[T: Copyable & Comparable & ImplicitlyDeletable]

A List-backed binary max-heap.

push and pop have complexity O(log(n)) where n = len(self)

Examples:

from std.collections.binary_heap import BinaryHeap
var heap = BinaryHeap[Int]()
heap.push(5)
heap.push(10)
heap.push(3)

print(heap.peek()) # 10
print(heap.pop()) # 10
print(heap.pop()) # 5
print(heap.pop()) # 3

Parameters

• ​T (Copyable & Comparable & ImplicitlyDeletable): Element type.

Implemented traits

AnyType, Copyable, Defaultable, ImplicitlyDeletable, Movable, Sized

Methods

__init__

def __init__(out self)

Constructs an empty heap.

def __init__(out self, *, capacity: Int)

Constructs a heap with a given capacity.

Args:

• ​capacity (Int): The capacity of the heap.

__len__

def __len__(self) -> Int

Gets the size of the binary heap.

Returns:

Int: The number of elements in the heap.

clear

def clear(mut self)

Clears the elements in the heap.

push

def push(mut self, var val: T)

Adds a value to the heap.

Args:

• ​val (T): The value to add.

pop

def pop(mut self) -> T

Removes the largest item from the heap and returns it.

Aborts if the heap is empty.

Returns:

T: The largest item in the heap.

peek

def peek(self) -> ref[self._data] T

Gets a reference to the largest element in the heap.

Examples:

from std.collections.binary_heap import BinaryHeap
var heap = BinaryHeap[Int]()
heap.push(1)
heap.push(2)
var two = heap.peek() # returns a reference to "2"

Returns:

ref[self._data] T: The largest element in the heap.