Version 6 (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 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*`)`

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 list.

`(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 vector.

## Queues

Queues are mutable ordered collections that can contain any Scheme object. Objects can be added to or removed from either end of a queue. They are intended to be a thin veneer over lists. Queues are disjoint from other types of Scheme objects.

## Procedures

`(make-queue)`

Returns a newly allocated empty queue.

`(queue `*element*` ...)`

Returns a newly allocated queue containing the *elements*. This operation should be O(n) in the size of the queue.

`(copy-queue` *queue*`)`

Returns a newly allocated queue containing the elements of *queue*.

`(queue? `*obj*`)`

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

`(queue-length `*queue*`)`

Returns the number of elements in *queue*.

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

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

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

`(queue-first `*queue*` `*element*`)`

Returns the first element of the queue. This operation should be O(1).

`(queue-last`*queue*` `*element*`)`

Returns the last element of the queue. This operation should be O(1).

`(queue-add-first! `*queue*` `*element*`)`

Adds *element* to the beginning of *queue*. Returns an unspecified value. This operation should be O(1).

`(queue-add-last! `*queue*` `*element*`)`

Adds *element* to the end of *queue*. Returns an unspecified value. This operation should be O(1).

`(queue-remove-first! `*queue*`)`

Removes the first element of the queue and returns it. This operation should be O(1).

`(queue-remove-last! `*queue*`)`

Removes the last element of the queue and returns it. This operation should be O(1).

**Issue:** Maybe return an unspecified result instead? Returning the removed value is convenient but contrary to the usual Scheme style.

`(queue-map `*proc queue*`)`

Applies *proc* to each element of *queue* in order and returns a newly allocated queue containing the results. This operation should be O(N) in the size of the queue.

`(queue-for-each `*proc*` `*queue*`)`

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

`(queue->list `*queue*`)`

Returns a list containing the members of *queue* in order. It is an error to mutate the result of this procedure, as it may share storage with the queue. This operation should be O(N) in the size of the queue.

`(list->queue ``''<''` `''list''`)`

Returns a newly allocated queue containing the elements of *list* in order. It is an error to mutate *list* after calling this procedure, as it may share storage with the queue. This operation should be O(n) in the size of the heap.

`(queue->vector `*queue*`)`

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

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

Returns a newly allocated queue containing the elements of *vector* in order. This operation should be O(n) in the size of the vector.