Standard library · Collections

coll/heap

Imported as import "coll/heap" as heap, its names are then heap.…. Every signature below is the one the checker infers.

A priority queue: the least element is always at the top, and taking it costs a logarithm. A heap is a value — push and pop give a new heap and leave the old one as it was — so one can be kept, passed along, or sent down a channel, and two strands never contend for it.

The order is < unless the heap was made with new_with(before), where before(a, b) says whether a comes out before b — so a heap of (priority, task) pairs can order by the priority alone, and a max-heap is new_with(\a, b -> a > b). This is a leftist heap: merging two is a walk down their right spines, which are short by construction.

h = heap.of(Cons(5, Cons(1, Cons(3, Nil))))
heap.peek(h)                         # => Some(1)
heap.pop(h) |> opt_map(\p -> fst(p))   # => Some(1)
heap.sorted(h)                       # => Cons(1, Cons(3, Cons(5, Nil)))

Types

`Heap(a)`

Heap(before: (a, a) -> Bool, root: Tree(a), size: Int)

`Tree(a)`

Leaf
Node(rank: Int, item: a, left: Tree(a), right: Tree(a))

Functions

`fn new() -> Heap('a) # where 'a is ordered`

heap.size(heap.new())   # => 0

`fn new_with(before: ('a, 'a) -> Bool) -> Heap('a)`

h = heap.push(heap.push(heap.new_with(\a, b -> a > b), 1), 9)
heap.peek(h)   # => Some(9)

`fn of(items: List('a)) -> Heap('a) # where 'a is ordered`

heap.sorted(heap.of(Cons("pear", Cons("apple", Nil))))   # => Cons(apple, Cons(pear, Nil))

`fn of_with(items: List('a), before: ('a, 'a) -> Bool) -> Heap('a)`

h = heap.of_with(Cons((2, "b"), Cons((1, "a"), Nil)), \x, y -> fst(x) < fst(y))
heap.peek(h)   # => Some((1, a))

`fn push(h: Heap('a), x: 'a) -> Heap('a)`

heap.sorted(heap.push(heap.of(Cons(2, Nil)), 1))   # => Cons(1, Cons(2, Nil))

`fn peek(h: Heap('a)) -> Option('a)`

heap.peek(heap.of(Cons(3, Cons(2, Nil))))   # => Some(2)
heap.peek(heap.new())                        # => None

`fn pop(h: Heap('a)) -> Option(('a, Heap('a)))`

The least element and the heap without it, or None when it is empty.

h = heap.of(Cons(3, Cons(2, Nil)))
heap.pop(h) |> opt_map(\p -> fst(p))                # => Some(2)
heap.pop(h) |> opt_map(\p -> heap.sorted(snd(p)))   # => Some(Cons(3, Nil))

`fn size(h: Heap('a)) -> Int`

heap.size(heap.of(Cons(3, Cons(2, Nil))))   # => 2

`fn is_empty(h: Heap('a)) -> Bool`

heap.is_empty(heap.new())   # => true

`fn merge(a: Heap('a), b: Heap('a)) -> Heap('a)`

Both heaps as one; they must have been made with the same order.

heap.sorted(heap.merge(heap.of(Cons(4, Cons(1, Nil))), heap.of(Cons(3, Nil))))   # => Cons(1, Cons(3, Cons(4, Nil)))

`fn sorted(h: Heap('a)) -> List('a)`

Everything, least first.

heap.sorted(heap.of(Cons(2, Cons(2, Cons(1, Nil)))))   # => Cons(1, Cons(2, Cons(2, Nil)))

Tests

test_least_first
test_a_heap_is_a_value
test_another_order
test_many

← coll/deque coll/set →