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 vectors. Binary heaps are disjoint from other types of Scheme objects.
(make-heap <)
Returns a newly allocated empty heap. < is the less-than procedure for the heap.
(heap < element ...)
Returns a newly allocated 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)
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 < heap)
Applies proc to each element of heap in arbitrary order and returns a newly allocated 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 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)
Returns a newly allocated 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)
Returns a newly allocated list containing the members of heap in increasing order. Heap may be destroyed in the process.
(list->heap < list)
Returns a newly allocated heap containing the elements of list and using < as the ordering procedure. This operation should be O(n) in the size of the list.
(heap->vector heap)
Returns a newly allocated vector containing the elements of heap in arbitrary order.
(heap->sorted-vector! < heap)
Returns a newly allocated vector containing the elements of heap in increasing order. Heap may be destroyed in the process.
(vector->heap < vector)
Returns a newly allocated heap containing the elements of vector and using < as the ordering procedure. This operation should be O(n) in the size of the vector.