vheap

heap_new()

Builds a new, empty heap.

heap_new()

heap_is_empty(heap)

Tests whether heap has no elements.

heap_is_empty(heap_new())

heap_push(heap, priority, item)

Gives back a new heap with (priority, item) inserted.

heap_push(heap_push(heap_new(), 5, "b"), 1, "a")

heap_peek_min(heap)

Gives back the (priority, item) Tuple with the smallest priority, without removing it.

heap_peek_min(heap_push(heap_push(heap_new(), 5, "b"), 1, "a"))

heap_pop_min(heap)

Removes and gives back the minimum-priority element, along with the resulting heap.

heap_pop_min(heap_push(heap_push(heap_new(), 5, "b"), 1, "a"))

heap_from_list(items, key_fn)

Builds a heap from every element of items, keyed by key_fn.

use "stdlib/func.ven"
heap_from_list([3, 1, 2], identity)

k_smallest(items, k, key_fn)

Gives back the k smallest elements of items, ordered from smallest to largest, by key_fn.

use "stdlib/func.ven"
k_smallest([5, 3, 8, 1, 9], 2, identity)

heap4_new()

heap4_comparison_count(h)

heap4_contains(h, id)

Tests whether id currently has an entry in h.

smallest_int_pair(a, b)

Internal: the smaller of two Integers, without pulling in a List allocation for the sake of one comparison on the sift-down hot path.

heap4_push(h, id, priority)

Inserts a brand-new id with priority.

h = heap4_new()
heap4_push(h, "a", 5)

heap4_peek_min(h)

Gives back (priority, id) for the minimum entry, without removing it.

heap4_priority_of(h, id)

The current priority stored for id.

heap4_pop_min(h)

Removes and gives back (priority, id) for the minimum entry, in place.

heap4_decrease_key(h, id, new_priority)

Lowers the priority of the already-present id to new_priority, in place, sifting up as needed.

h = heap4_new()
heap4_push(h, "a", 10)
heap4_decrease_key(h, "a", 3)

heap4_from_pairs(pairs)