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 12

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.

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

`(heap? `''obj''`)`

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

`(heap-size `''heap''`)`

Returns the number of elements in ''heap''.

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

Returns `#t` if ''element'' is a member of ''heap'' (in the sense of the comparator) 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-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-remove-min! `''heap'' ''element''`)`

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

time

2014-09-21 10:15:04