Version 5 (modified by cowan, 5 years ago) (diff) |
---|

## Binary heaps

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

## Procedures

`(make-heap `*<*`)`

Returns a newly allocated empty heap. *<* is the less-than procedure for the heap.

`(heap `*<*` `*element*` ...)`

Returns a newly allocated heap using *<* as the ordering procedure, and containing the *elements*. This operation should be O(n) in the size of the heap.

`(copy-heap` *heap*`)`

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

`(heap? `*obj*`)`

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

`(heap-length `*heap*`)`

Returns the number of elements in *heap*.

**Issue:** change the name to `heap-size` or `heap-count`?

`(heap-member? `*heap*` `*element*`)`

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

`(heap-add! `*heap*` `*element*`)`

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

`(heap-minimum `*heap*` `*element*`)`

Returns the smallest element of the heap (according to the *<* function). This operation should be O(log N) in the size of the heap.

`(heap-remove-minimum! `*heap*` `*element*`)`

Removes the smallest element of the heap (according to the *<* function) and returns it. This operation should be O(log N) in the size of the heap.

`(heap-map `*proc*` `*<*` `*heap*`)`

Applies *proc* to each element of *heap* in arbitrary order and returns a newly allocated heap with ordering predicate *<* 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 *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*`)`

Returns a newly allocated list containing the members of *heap* in arbitrary order. This operation should be O(N) in the size of the heap.

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

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

`(list->heap `*<*` `*list*`)`

Returns a newly allocated heap containing the elements of *list* and using *<* as the ordering procedure. This operation should be O(n) in the size of the heap.

`(heap->vector `*heap*`)`

Returns a newly allocated vector containing the elements of *heap* in arbitrary order.

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

Returns a newly allocated vector containing the elements of *heap* in increasing order. *Heap* may be destroyed in the process.

`(vector->heap `*<*` `*vector*`)`

Returns a newly allocated heap containing the elements of *vector* and using *<* as the ordering procedure. This operation should be O(n) in the size of the heap.