`std/collections/heap`

std/collections/src/heap.trb

The priority structure: Heap, a binary heap over a List that hands out the item with the smallest key first.

It is not a Queue and has no trait: a queue gives items back in the order they went in, a heap does not, and a trait with one implementation is a name for nothing. The order is a value the heap carries (Heap.by { _.priority }), so no Compare bound sits on Item.

type Heap

type Heap<Item> with Iterate<Item>, Length

A heap: removeSmallest takes out the item whose key is the smallest, peekSmallest looks at it. The key is a function from an item to an Int, given once when the heap is built and kept for its life.

Ties. Items with equal keys come out in no promised order. Put the tie-break into the key (priority * 1000 + sequence) if it matters.

Iteration hands out the items in the order removeSmallest would, smallest key first, without changing the heap. It sorts a copy, so it costs O(n log n); length and isEmpty come with the heap and cost O(1).

Cost

Operation	Cost
`insert`, `removeSmallest`	O(log n) key calls
`peekSmallest`, `length`, `clear`	O(1)
`iterate`, `toList`	O(n log n), smallest first

Examples

var waiting: Heap<Int> = Heap.by { number => number }
waiting.insert 5
waiting.insert 2
print waiting.peekSmallest()
print waiting.removeSmallest()

fn by

static fn by(key: (value: Item) => Int): Self

Builds an empty heap ordered by key: the item with the smallest key comes out first.

fn insert

var fn insert(value: Item)

Puts value into the heap, in place.

fn removeSmallest

var fn removeSmallest(): Item?

Takes the item with the smallest key out and answers it, or None if the heap is empty.

fn peekSmallest

fn peekSmallest(): Item?

The item removeSmallest would take, or None if the heap is empty. Nothing is changed.

fn clear

var fn clear()

Removes every item, in place.

fn length

fn length(): Int

How many items there are.

fn iterate

fn iterate(): Iterator<Item>

A cursor from the smallest key to the largest, over a sorted copy: the heap itself is not changed.