12.15 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> ¶

{data.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 ¶

{data.heap} 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 ¶

{data.heap} 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 ¶

{data.heap} Copy the heap. The backing storage is also copied.

Function: binary-heap-clear! heap ¶

{data.heap} Empty the heap.

Function: binary-heap-num-entries heap ¶

{data.heap} Returns the current number of entries in the heap.

Function: binary-heap-empty? heap ¶

{data.heap} Returns #t if the heap is empty, #f otherwise.

Function: binary-heap-push! heap item ¶

{data.heap} 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 ¶

{data.heap} 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 ¶

{data.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 ¶

{data.heap} 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 pred heap :optional failure ¶

{data.heap} 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, the thunk failure is called, whose default is (^[] #f). This is O(n) operation.

Note: The argument order used to be (binary-heap-find heap pred) until 0.9.10. We changed it to align other *-find procedures. The old argument order still work for the backward compatibility, but the new code should use the current order.

Function: binary-heap-remove! heap pred ¶

{data.heap} Remove all items in the heap that satisfy pred. This is O(n) operation.

Function: binary-heap-delete! heap item ¶

{data.heap} 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.