heap
The heap module is a heap of ints, floats or strings: pop gives the smallest value first (min_heap) or the largest (max_heap). Use it for the k smallest of a stream, merging sorted lists, or any "next lowest" loop. For values that aren't ordered themselves, such as structs, use pqueue.
import heap
fn main():
h = heap.min_heap[int]()
for x in [5, 1, 9, 3]:
h.push(x)
print(h.peek(), h.len())
while h.pop() is Some(x):
print(x)
words = heap.heap_of(["pear", "apple", "fig"], true)
print(words.drain())Some(1) 4
1
3
5
9
["pear", "fig", "apple"]Functions
fn min_heap[T: Ord]() Heap[T] empty; pop gives the smallest first
fn max_heap[T: Ord]() Heap[T] empty; pop gives the largest first
fn heap_of[T: Ord](xs: [T], max: bool) Heap[T] from an array, in O(n)
fn push[T: Ord](h: mut Heap[T], x: T) O(log n)
fn pop[T: Ord](h: mut Heap[T]) Option[T] the next value, or None when empty; O(log n)
fn peek[T](h: Heap[T]) Option[T] the next value, left in
fn len[T](h: Heap[T]) int
fn is_empty[T](h: Heap[T]) bool
fn drain[T: Ord](h: mut Heap[T]) [T] every value in pop order, leaving h emptyT is int, float or str. A heap is a value like any other: h2 = h copies it, and the functions that change one take it mut, so h.push(x) is push(&h, x).
How it works, and speed
The heap is 4-ary: each value has up to four children, side by side in memory. That halves the levels of a binary heap, so pop, which moves the hole at the top down to a leaf by the best child and then lets the old last value rise, takes about half the cache misses. A heap that has held 4096 values or more gives its memory back when pop empties it.
bench/std pushes 2 million ints and pops them all: Tern 115 ms, Rust's BinaryHeap (binary) 129 ms, Go's container/heap 411 ms.