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