Binary heaps are mutable collections that can contain any Scheme object provided there exists a total ordering on the objects expressed by a SRFI 114 comparator. They are intended to be a thin veneer over vectors. Binary heaps are disjoint from other types of Scheme objects.

(heap *comparator* *element* ...)

Returns a newly allocated heap ordered by *comparator*, and containing the *elements*. This operation should be O(n) in the size of the heap.

(heap? *obj*)

Returns #t if *obj* is a heap, and #f otherwise.

(heap-contains? *heap* *element*)

Returns #t if *element* is a member of *heap* (in the sense of the comparator) and #f otherwise.

(heap-min *heap* *element*)

Returns the smallest element of the heap (in the sense of the comparator). This operation should be O(log N) in the size of the heap.

(heap-adjoin! *heap* *element*)

Adds *element* to *heap*. Returns an unspecified value. This operation should be O(log N) in the size of the heap.

(heap-pop! *heap*)

Removes the smallest element of the heap (in the sense of the comparator) and returns it. This operation should be O(log N) in the size of the heap.

(heap-pop-adjoin! *heap* *element*)

Removes the smallest element of the heap (in the sense of the comparator), pushes *element* on the heap, and returns the popped value. This operation should be O(log N) in the size of the heap.

(heap-adjoin-pop! *heap* *element*)

Pushes *element* on the heap, then removes the smallest element of the heap (in the sense of the comparator) and returns it. This operation should be O(log N) in the size of the heap.

(heap-pop-elements! *heap n*)

Returns a list containing the *n* smallest elements popped from *heap*.

(heap-copy *heap*)

Returns a newly allocated heap containing the elements of *heap* with the same *<* procedure.

(heap-size *heap*)

Returns the number of elements in *heap*.

(heap-map *proc* *comparator* *heap*)

Applies *proc* to each element of *heap* in arbitrary order and returns a newly allocated heap ordered by *comparator* and containing the values of the applications. This operation should be O(N) in the size of the heap.

(heap-for-each *proc* *heap*)

Applies *proc* to each element of *heap* in arbitrary order, discarding the returned values. Returns an unspecified value. This operation should be O(N) in the size of the heap.

(heap->list *heap*)

(heap->vector *heap*)

Returns a newly allocated list or vector containing the members of *heap* in arbitrary order.

(list->heap *comparator* *list*)

(vector->heap *comparator* *vector*)

Returns a newly allocated heap containing the elements of *list* or *vector* and ordered by *comparator*.

(heap->sorted-list! *heap*)

(heap->sorted-vector! *heap*)

Returns a newly allocated list or vector containing the members of *heap* in increasing order. *Heap* will be destroyed in the process.

(heap->generator *heap*)

Returns a generator that yields the elements of *heap* in increasing order, destroying *heap* in the process.

(generator->heap *comparator generator*)

Returns a heap built using *comparator* and the values of *generator*.