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 3

author

cowan

comment

ipnr

74.68.112.189

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 an ''ordering procedure''.  They are intended to be a thin veneer over arrays.  Binary heaps are disjoint from other types of Scheme objects.

== Procedures ==

`(make-heap `''<''`)`

Constructs and returns a new empty heap.  ''<'' is the less-than procedure for the heap.

`(heap `''<''` `''element''` ...)`

Constructs and returns a new 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''`)`

Constructs and returns a new 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.

'''Issue:''' maybe this should return an unspecified value like other destructive procedures?

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

Applies ''proc'' to each element of ''heap'' in arbitrary order and constructs and returns a new 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''`)`

Constructs and returns a new 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''`)`

Constructs and returns a new list containing the members of ''heap'' in increasing order.  ''Heap'' may be destroyed in the process.

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

Constructs and returns a new 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''`)`

Constructs and returns a new vector containing the elements of ''heap'' in arbitrary order.

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

Constructs and returns a new vector containing the elements of ''heap'' in increasing order.  ''Heap'' may be destroyed in the process.

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

Constructs and returns a new heap containing the elements of ''vector'' and using ''<'' as the ordering procedure.  This operation should be O(n) in the size of the heap.

time

2011-05-14 12:33:39