A heap is an implementation of a priority queue, which is a structure that maintains a sorted set of elements. The key property is that insertion of an arbitrary element and removal of the first element (determined by order) is performed in O(log n) time.

Heap elements are key/value pairs and are compared using the <=> generic word on the first element of the pair.

There are two classes of heaps. Min-heaps sort their elements so that the minimum element is first:

min-heap

min-heap? ( object -- ? )

<min-heap> ( -- min-heap )

Max-heaps sort their elements so that the maximum element is first:

max-heap

max-heap? ( object -- ? )

<max-heap> ( -- max-heap )

Both obey a protocol.

Queries:

heap-empty? ( heap -- ? )

heap-size ( heap -- n )

heap-peek ( heap -- value key )

Insertion:

heap-push ( value key heap -- )

heap-push* ( value key heap -- entry )

heap-push-all ( assoc heap -- )

Removal:

heap-pop* ( heap -- )

heap-pop ( heap -- value key )

heap-delete ( entry heap -- )

Processing heaps:

slurp-heap ( ... heap quot: ( ... value key -- ... ) -- ... )