Binary heaps are mutable collections that can contain any Scheme object provided there exists a total ordering on the objects expressed by a SRFI 114 comparator. They are intended to be a thin veneer over vectors. Binary heaps are disjoint from other types of Scheme objects.
(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.
(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 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.
(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.
(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.