This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home.
Source for wiki BinaryHeapsCowan version 7
author
cowan
comment
ipnr
198.185.18.207
name
BinaryHeapsCowan
readonly
0
text
== 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''.
`(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).
`(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.
time
2013-05-20 19:29:59
version
7