Next: Immutable deques, Previous: Cache, Up: Library modules - Utilities [Contents][Index]

`data.heap`

- Heap- Module:
**data.heap** -
A heap is a data container that allows efficient retrieval of the minimum or maximum entry. Unlike a

`<tree-map>`

(see Treemaps), which always keeps all entries in order, a heap only cares the minimum or the maximum of the current set; the other entries are only partially ordered, and reordered when the minimu/maximum entry is removed. Hence it is more efficient than a treemap if all you need is minimum/maximum value. Besides binary heaps can store entries in packed, memory-efficient way.

- Class:
**<binary-heap>** -
An implementation of a binary heap. Internally it uses min-max heap, so that you can find both minimum and maximum value in O(1). Pushing a new value and popping the minimum/maximum value are both O(log n).

It also stores its values in a flat vector, a lot more compact than a general tree structure that needs a few pointers per node. By default it uses a sparse vector for the backing storage, allowing virtually unlimited capacity (see Sparse vectors). But you can use an ordinal vector or a uniform vector as a backing storage instead.

A binary heap isn’t MT-safe structure; you must put it in atom or use mutexes if multiple threads can access to it (see Synchronization primitives).

- Function:
**make-binary-heap***:key comparator storage key* Creates and returns a new binary heap.

The

`comparator`keyword argument specifies how to compare the entries. It must have comparison procedure or ordering predicate. The default is`default-comparator`

. See Basic comparators, for the details of comparators.The

`storage`keyword argument gives alternative backing storage. It must be either a vector, a uniform vector, or an instance of a sparse vector (see Sparse vectors). The default is an instance of`<sparse-vector>`

. If you pass a vector or a uniform vector, it determines the maximum number of elements the heap can hold. The heap won’t be extend the storage once it gets full.The

`key`keyword argument must be a procedure; it is applied on each entry before comparison. Using key procedure allows you to store auxiliary data other than the actual value to be compared. The following example shows the entries are compared by their`car`

’s:(define *heap* (make-binary-heap :key car)) (binary-heap-push! *heap* (cons 1 'a)) (binary-heap-push! *heap* (cons 3 'b)) (binary-heap-push! *heap* (cons 1 'c)) (binary-heap-find-min *heap*) ⇒ (1 . c) (binary-heap-find-max *heap*) ⇒ (3 . b)

- Function:
**build-binary-heap***storage :key comparator key num-entries* Create a heap from the data in

`storage`, and returns it. (Sometimes this operation is called*heapify*.) This allows you to create a heap without allocating a new storage. The`comparator`and`key`arguments are the same as`make-binary-heap`

.`Storage`must be either a vector, a uniform vector, or an instance of a sparse vector. The storage is modified to satisfy the heap property, and will be used as the backing storage of the created heap. Since the storage will be owned by the heap, you shouldn’t modify the storage later.The storage supposed to have keys from index 0 below

`num-entries`. If`num-entries`is omitted or`#f`

, entire vector or uniform vector, or up to`sparse-vector-num-entries`

on the sparse vector, is heapified.

- Function:
**binary-heap-copy***heap* Copy the heap. The backing storage is also copied.

- Function:
**binary-heap-clear!***heap* Empty the heap.

- Function:
**binary-heap-num-entries***heap* Returns the current number of entries in the heap.

- Function:
**binary-heap-empty?***heap* Returns

`#t`

if the heap is empty,`#f`

otherwise.

- Function:
**binary-heap-push!***heap item* Insert

`item`into the`heap`. This is O(log n) operation. If the heap is already full, an error is raised.

- Function:
**binary-heap-find-min***heap :optional fallback* - Function:
**binary-heap-find-max***heap :optional fallback* Returns the minimum and maximum entry of the heap, respectively. The heap will be unmodified. This is O(1) operation.

If the heap is empty,

`fallback`is returned when it is provided, or an error is signaled.

- Function:
**binary-heap-pop-min!***heap* - Function:
**binary-heap-pop-max!***heap* Removes the minimum and maximum entry of the heap and returns it, respectively. O(log n) operation. If the heap is empty, an error is signaled.

The following procedures are not heap operations, but provided for the convenience.

- Function:
**binary-heap-swap-min!***heap item* - Function:
**binary-heap-swap-max!***heap item* These are operationally equivalent to the followings, respectively:

(begin0 (binary-heap-pop-min! heap) (binary-heap-push! heap item)) (begin0 (binary-heap-pop-max! heap) (binary-heap-push! heap item))

However, those procedures are slightly efficient, using heap property maintaining procedure only once per function call.

- Function:
**binary-heap-find***heap pred* Returns an item in the heap that satisfies

`pred`. If there are more than one item that satisfy`pred`, any one of them can be returned. If no item satisfy`pred`,`#f`

is returned. This is O(n) operation.

- Function:
**binary-heap-remove!***heap pred* Remove all items in the heap that satisfy

`pred`. This is O(n) operation.

- Function:
**binary-heap-delete!***heap item* Delete all items in the heap that are equal to

`item`, in terms of the heap’s comparator and key procedure. This is O(n) operation.Note that the key procedure is applied to

`item`as well before comparison.

Next: Immutable deques, Previous: Cache, Up: Library modules - Utilities [Contents][Index]