Skip to main content

(lispkit heap)

Library (lispkit heap) provides an implementation of a priority queue in form of a binary max heap. A max heap is a tree-based data structure in which for any given node C, if P is a parent node of C, then the value of P is greater than or equal to the value of C. Heaps as implemented by (lispkit heap) are mutable objects.


heap-type-tag constant

Symbol representing the heap type. The type-for procedure of library (lispkit type) returns this symbol for all heap objects.

(make-heap pred<?) procedure

Returns a new empty binary max heap with pred<? being the associated ordering function.

(heap-empty? hp) procedure

Returns #t if the heap hp is empty, otherwise #f is returned.

(heap-max hp) procedure

Returns the largest item in heap hp, i.e. the item which is larger than all others according to the comparison function of hp. Note, heap-max does not remove the largest item as opposed to heap-delete-max!. If there are no items on the heap, an error is signaled.

(heap-add! hp e1 ...) procedure

Inserts an item into the heap. The same item can be inserted multiple times.

(heap-delete-max! hp) procedure

Returns the largest item in heap hp, i.e. the item which is larger than all others according to the comparison function of hp, and removes the item from the heap. If there are no items on the heap, an error is signaled.

(heap-clear! hp) procedure

Removes all items from hp. After this procedure has been executed, the heap is empty.

(heap-copy hp) procedure

Returns a copy of heap hp.

(heap->vector hp) procedure

Returns a new vector containing all items of the heap hp in descending order. This procedure does not mutate hp.

(heap->list hp) procedure

Returns a list containing all items of the heap hp in descending order.

(heap->reversed-list hp) procedure

Returns a list containing all items of the heap hp in ascending order.

(list->heap! hp items) procedure

Inserts all the items from list items into heap hp.

(list->heap items pred<?) procedure

Creates a new heap for the given ordering predicate pred<? and inserts all the items from list items into it. list-\>heap returns the new heap.

(vector->heap vec pred<?) procedure

Creates and returns a new heap for the given ordering predicate pred<? and inserts all the items from vector vec into it.