(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

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

(make-heap pred<?)

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

(heap-empty? hp)

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

(heap-max hp)

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

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

(heap-delete-max! hp)

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)

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

(heap-copy hp)

Returns a copy of heap hp.

(heap->vector hp)

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

(heap->list hp)

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

(heap->reversed-list hp)

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

(list->heap! hp items)

Inserts all the items from list items into heap hp.

(list->heap items pred<?)

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<?)

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