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