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 13

author

cowan

comment


    

ipnr

127.11.51.1

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

=== Constructors ===

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

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

=== Predicates ===

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

=== Accessors ===

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

=== Mutators ===

`(heap-push! `''heap'' ''element''`)`

Adds ''element'' to ''heap''.  Returns an unspecified value.  This operation should be O(log N) in the size of the heap.

`(heap-pop! `''heap''`)`

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-pop-push! `''heap'' ''element''`)`

Removes the smallest element of the heap (in the sense of the comparator), pushes ''element'' on the heap, and returns the popped value.  This operation should be O(log N) in the size of the heap.

`(heap-push-pop! `''heap'' ''element''`)`

Pushes ''element'' on the heap, then 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-pop-elements! `''heap n''`)`

Returns a list containing the ''n'' smallest elements popped from ''heap''.

=== Mapping ===

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

=== Conversion ===

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

=== Generator functions ===

`(heap->generator `''heap''`)`

Returns a generator that yields the elements of ''heap'' in order, destroying ''heap'' in the process.

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

Returns a heap built using ''comparator'' and the values of ''generator''.


time

2014-11-19 03:20:54

version

13