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.
Queues are mutable ordered collections that can contain any Scheme object. Objects can be added to or removed from either end of a queue. They are intended to be a thin veneer over lists. Queues are disjoint from other types of Scheme objects.
(make-queue)
Returns a newly allocated empty queue.
(queue element ...)
Returns a newly allocated queue containing the elements. This operation should be O(n) in the size of the queue.
(copy-queue queue)
Returns a newly allocated queue containing the elements of queue.
(queue? obj)
Returns #t if obj is a queue, and #f otherwise.
(queue-length queue)
Returns the number of elements in queue.
(queue-member? queue element)
Returns #t if element is a member of queue (in the sense of eqv?) and #f otherwise.
(queue-first queue element)
Returns the first element of the queue. This operation should be O(1).
(queue-lastqueue element)
Returns the last element of the queue. This operation should be O(1).
(queue-add-first! queue element)
Adds element to the beginning of queue. Returns an unspecified value. This operation should be O(1).
(queue-add-last! queue element)
Adds element to the end of queue. Returns an unspecified value. This operation should be O(1).
(queue-remove-first! queue)
Removes the first element of the queue and returns it. This operation should be O(1).
(queue-remove-last! queue)
Removes the last element of the queue and returns it. This operation should be O(1).
(queue-map proc queue)
Applies proc to each element of queue in order and returns a newly allocated queue containing the results. This operation should be O(N) in the size of the queue.
(queue-for-each proc queue)
Applies proc to each element of queue in order, discarding the returned values. Returns an unspecified value. This operation should be O(N) in the size of the queue.
(queue->list queue)
Returns a list containing the members of queue in order. It is an error to mutate the result of this procedure, as it may share storage with the queue. This operation should be O(N) in the size of the queue.
`(list->queue < list)
Returns a newly allocated queue containing the elements of list in order. It is an error to mutate list after calling this procedure, as it may share storage with the queue. This operation should be O(n) in the size of the heap.
(queue->vector queue)
Returns a newly allocated vector containing the elements of heap in order.
(vector->queue< vector)
Returns a newly allocated queue containing the elements of vector in order. This operation should be O(n) in the size of the vector.