std/heap
On this page
Index
- type
Heap- method
Heap.push - method
Heap.pop - method
Heap.peek - method
Heap.get - method
Heap.remove - method
Heap.fix - method
Heap.len - method
Heap.is_empty - method
Heap.to_list
- method
- fn
new - fn
tracked - fn
from_list
Types
Heap
struct Heap[T] {
_items: List[T]
_less: fn(T, T) -> Bool
_moved: fn(T, Int)
}A binary heap: the element for which less holds against all others
comes out first. A value, as List: a copy shares the elements until one
of them is written. Equal elements come out in no particular order.
Heap.push
fn (var h: Heap[T]) push(x: T)Adds x in O(log n) (heap.Push).
Heap.pop
fn (var h: Heap[T]) pop() -> T?The least element, removed, in O(log n); None when empty (heap.Pop).
Heap.peek
fn (h: Heap[T]) peek() -> T?The least element, kept; None when empty.
Heap.get
fn (h: Heap[T]) get(i: Int) -> T?The element at heap position i (0 is the least); None out of range.
Heap.remove
fn (var h: Heap[T]) remove(i: Int) -> T?The element at position i, removed, in O(log n); None out of range (heap.Remove).
Heap.fix
fn (var h: Heap[T]) fix(i: Int, x: T)Replaces the element at position i by x and restores the order, in O(log n) (heap.Fix after changing it); a fault when i is out of range.
Heap.len
fn (h: Heap[T]) len() -> IntHeap.is_empty
fn (h: Heap[T]) is_empty() -> BoolHeap.to_list
fn (h: Heap[T]) to_list() -> List[T]The elements in heap order (the least first, the rest not sorted).
Functions
new
fn new[T](less: fn(T, T) -> Bool) -> Heap[T]An empty heap; less(a, b) is true when a comes out before b.
tracked
fn tracked[T](less: fn(T, T) -> Bool, moved: fn(T, Int)) -> Heap[T]An empty heap that calls moved(x, i) each time an element x lands at
position i (a push, a sift, the element a remove moves into the gap), so
a caller can keep the position of each element for remove and fix.
from_list
fn from_list[T](items: List[T], less: fn(T, T) -> Bool) -> Heap[T]The heap of items, in O(n) (heap.Init).
↑ index