9 Heaps

For all the procedures: the argument ITEM< must be a procedure accepting 2 arguments, being items from the heap, and returning #t if the first is less than the second; if the collected items are numbers: ITEM< can be <; if the collected items are strings: ITEM< can be string<?.

Function: make-heap ITEM<

Return a new empty heap which uses the given ordering procedure.

Function: heap ITEM< item …

Return a new heap, ordered by the procedure argument ITEM<, that contains all the other arguments as items.

Function: heap? OBJ

Return #t if OBJ is a heap, #f otherwise.

Function: heap-size heap

Return a non–negative integer representing the number of items in heap.

Function: heap-empty? heap

Return #t if the heap contains no items, #f otherwise.

Function: heap-min heap

Return the minimum item in heap, according the heap’s ordering procedure. If there are no items: a pfds-heap-empty-condition condition is raised.

Function: heap-delete-min heap

Return a new heap containing all the items of heap, except for the minimum argument, as determined by the heap’s ordering procedure. If there are no items: raise a condition with kind pfds-heap-empty.

Function: heap-empty-condition? OBJ

Return #t if OBJ is a condition with kind pfds-heap-empty; otherwise return #f.

Function: heap-pop heap

Return two values: the the minimum item in heap, and a heap obtained by removing the minimum value from the original heap. If heap is empty: raise a condition with kind pfds-heap-empty.

Function: heap-insert heap item

Return a new heap obtained by adding item to those in the heap.

Function: heap->list heap

Return a list containing all the items of heap. The items of the list are ordered according to the heap’s ordering procedure.

Function: list->heap list-of-items ITEM<

Return a heap containing all the items of the given list, using the procedure argument ITEM< to order them.

Function: heap-merge heap1 heap2

Return the heap containing all the items of the argument heaps. The argument heaps are assumed to be using the same ordering procedure.

Function: heap-sort ITEM< list-of-items

Return a new list that is a permutation of the list-of-items, such that all the items are ordered by the given procedure ITEM<.

Function: heap-ordering-procedure heap

Return the ordering procedure used internally by heap.

This document describes version 0.5.0-devel.1 of MMCK PFDS.