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. For a version of this page that may be more recent, see BinaryHeapsCowan in WG2's repo for R7RS-large.

Binary­Heaps­Cowan

cowan
2011-08-10 11:29:40
4history
source

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)

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