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 9

author

cowan

comment

ipnr

127.11.51.1

name

BinaryHeapsCowan

readonly

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 a [http://srfi.schemers.org/srfi-114/srfi-114.html SRFI 114] comparator.  They are intended to be a thin veneer over vectors.  Binary heaps are disjoint from other types of Scheme objects.

== Procedures ==

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

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

`(heap->sorted-list! `''heap''`)`

`(heap->sorted-vector! `''heap''`)`

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

`(list->heap `''comparator''` `''list''`)`

Returns a newly allocated heap containing the elements of ''list'' and ordered by ''comparator''.

`(vector->heap `''comparator''` `''vector''`)`

Returns a newly allocated heap containing the elements of ''vector'' and ordered by ''comparator''.

time

2014-08-04 07:49:21