std::heap
A priority queue (a binary heap): pop gives the smallest element by cmp. For largest first, store a type whose cmp is reversed.
Source: std/heap.volt
Types
struct std::heap
<T: type, Allocator: std::mem::allocator = std::mem::default_allocator> struct heapA binary min-heap: push and pop in O(log n), peek in O(1).
| Field | |
|---|---|
items: std::vec<T, Allocator> = {} | items[i] sorts no earlier than items[(i - 1) / 2] |
Methods
<T: type, A: std::mem::allocator> attach fn new_in(static this: std::heap<T>, allocator: A) -> std::heap<T, A>an empty heap that allocates from allocator
<T: type, A: std::mem::allocator> attach fn reserve(this: std::heap<T, A>&, n: usize) -> std::mem::mem_error!voidroom for n elements without growing
<T: type, A: std::mem::allocator> attach fn len(this: std::heap<T, A>&) -> usizehow many elements it holds
<T: type, A: std::mem::allocator> attach fn peek(this: std::heap<T, A>&) -> T*the smallest element, or null when empty
<T: type, A: std::mem::allocator> attach fn push(this: std::heap<T, A>&, value: T) -> voidadd value (unchecked: i starts at len - 1 and only goes to (i - 1) / 2, below it)
<T: type, A: std::mem::allocator> attach fn pop(this: std::heap<T, A>&) -> T?the smallest element, moved out (unchecked: len > 0; a child is read only below len, and i is always 0 or a child read before)
<T: type, A: std::mem::allocator> attach fn clear(this: std::heap<T, A>&) -> voiddelete every element