This is the cl-heap Reference Manual, version 0.1.6, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Dec 15 05:01:19 2024 GMT+0.
The main system appears first, followed by any subsystem dependency.
cl-heapAn implementation of heap and priority queue data structures.
Rudy Neeser <rudy.neeser@gmail.com>
GPLv3
0.1.6
package.lisp (file).
condition.lisp (file).
heap.lisp (file).
binary-heap.lisp (file).
fibonacci-heap.lisp (file).
priority-queue.lisp (file).
Files are sorted by type and then listed depth-first from the systems components trees.
cl-heap/cl-heap.asdcl-heap/package.lispcl-heap/condition.lispcl-heap/heap.lispcl-heap/binary-heap.lispcl-heap/fibonacci-heap.lispcl-heap/priority-queue.lispcl-heap/condition.lisppackage.lisp (file).
cl-heap (system).
heap-error (condition).
key-error (condition).
heap-error-message (reader method).
cl-heap/heap.lispcondition.lisp (file).
cl-heap (system).
add-all-to-heap (generic function).
add-to-heap (generic function).
decrease-key (generic function).
delete-from-heap (generic function).
empty-heap (generic function).
heap (class).
heap-key (reader method).
heap-size (generic function).
heap-sorting-function (reader method).
is-empty-heap-p (generic function).
merge-heaps (generic function).
nmerge-heaps (generic function).
peep-at-heap (generic function).
pop-heap (generic function).
print-object (method).
compare-items (generic function).
cl-heap/binary-heap.lispheap.lisp (file).
cl-heap (system).
add-all-to-heap (method).
add-to-heap (method).
binary-heap (class).
binary-heap-extension-factor (reader method).
(setf binary-heap-extension-factor) (writer method).
decrease-key (method).
delete-from-heap (method).
empty-heap (method).
heap-size (method).
initialize-instance (method).
is-empty-heap-p (method).
merge-heaps (method).
nmerge-heaps (method).
peep-at-heap (method).
pop-heap (method).
children-positions (function).
parent-position (function).
percolate-down (generic function).
percolate-up (generic function).
cl-heap/fibonacci-heap.lispbinary-heap.lisp (file).
cl-heap (system).
add-all-to-heap (method).
add-to-heap (method).
decrease-key (method).
delete-from-heap (method).
empty-heap (method).
fibonacci-heap (class).
heap-size (method).
initialize-instance (method).
is-empty-heap-p (method).
merge-heaps (method).
nmerge-heaps (method).
peep-at-heap (method).
pop-heap (method).
print-object (method).
concatenate-node-lists (generic function).
cut-node (generic function).
delete-node (generic function).
do-each-node (macro).
is-node-root-p (generic function).
link (generic function).
mark-node (generic function).
meld (generic function).
node (class).
node-child (reader method).
(setf node-child) (writer method).
node-item (reader method).
(setf node-item) (writer method).
node-last (reader method).
(setf node-last) (writer method).
node-marked-p (reader method).
(setf node-marked-p) (writer method).
node-next (reader method).
(setf node-next) (writer method).
node-parent (reader method).
(setf node-parent) (writer method).
node-rank (reader method).
(setf node-rank) (writer method).
unmark-node (generic function).
cl-heap/priority-queue.lispfibonacci-heap.lisp (file).
cl-heap (system).
dequeue (generic function).
empty-queue (generic function).
enqueue (generic function).
initialize-instance (method).
peep-at-queue (generic function).
priority-queue (class).
queue-size (generic function).
Packages are listed by definition order.
cl-heapAn implementation of heap and priority queue data structures.
common-lisp.
add-all-to-heap (generic function).
add-to-heap (generic function).
binary-heap (class).
binary-heap-extension-factor (generic reader).
(setf binary-heap-extension-factor) (generic writer).
decrease-key (generic function).
delete-from-heap (generic function).
dequeue (generic function).
empty-heap (generic function).
empty-queue (generic function).
enqueue (generic function).
fibonacci-heap (class).
heap (class).
heap-error (condition).
heap-key (generic reader).
heap-size (generic function).
heap-sorting-function (generic reader).
is-empty-heap-p (generic function).
key-error (condition).
merge-heaps (generic function).
nmerge-heaps (generic function).
peep-at-heap (generic function).
peep-at-queue (generic function).
pop-heap (generic function).
priority-queue (class).
queue-size (generic function).
children-positions (function).
compare-items (generic function).
concatenate-node-lists (generic function).
cut-node (generic function).
delete-node (generic function).
do-each-node (macro).
heap-error-message (generic reader).
is-node-root-p (generic function).
link (generic function).
mark-node (generic function).
meld (generic function).
node (class).
node-child (generic reader).
(setf node-child) (generic writer).
node-item (generic reader).
(setf node-item) (generic writer).
node-last (generic reader).
(setf node-last) (generic writer).
node-marked-p (generic reader).
(setf node-marked-p) (generic writer).
node-next (generic reader).
(setf node-next) (generic writer).
node-parent (generic reader).
(setf node-parent) (generic writer).
node-rank (generic reader).
(setf node-rank) (generic writer).
parent-position (function).
percolate-down (generic function).
percolate-up (generic function).
unmark-node (generic function).
Definitions are sorted by export status, category, package, and then by lexicographic order.
Adds a list of items to a HEAP. This can typically
be done more efficiently than by using repeated calls to
ADD-TO-HEAP, since the heap order only needs to be reinstated after
all of the items have been inserted, rather than maintained through
each operation. Returns the heap object.
fibonacci-heap) (items list)) ¶Adds the following list of items into the heap. This is an O(n) operation.
binary-heap) (items list)) ¶Adds all the items in the list into the BINARY-HEAP. This is a O(n + log(n)) = O(n) operation. Returns the BINARY-HEAP.
Inserts an item into the given HEAP data
structure. Returns two values: first, the item added, and then an
index-key which can be used to identify the item for DECREASE-KEY
and DELETE-FROM-HEAP operations.
fibonacci-heap) item) ¶Adds an item to a Fibonacci-heap. This is a constant time operation. Returns the item added to the heap.
binary-heap) item) ¶Inserts an item into a BINARY-HEAP. This is O(log(n)), n being the number of items in the heap.
binary-heap)) ¶binary-heap)) ¶The percentage at which the space
allocated for data in the heap should grow at
once that space has been exceeded.
Decreases the value of the item represented by
ITEM-INDEX. ITEM-INDEX is the index returned by ADD-TO-HEAP for a
particular item. VALUE is the item’s new value, and this must be
"less" than its old value. Returns the heap.
fibonacci-heap) (item-index node) value) ¶Changes the value of an item represented by the ITEM-INDEX to VALUE. This index is returned as the second argument to ADD-TO-HEAP. This is an amortised constant time operation.
binary-heap) (item-index integer) value) ¶Deceases the key of the item pointed to by ITEM-INDEX. The index is returned as the second value of ADD-TO-HEAP. The value of the item at the index is changed to VALUE, which should be less than its old value. This operation is O(log(n)), with n being the number of items in the heap. Note that using a binary heap is not ideal for this operation, since the item pointed to by any given index can be changed by performing any heap operation. This function is provided mostly for completeness.
Removes the item from the heap represented by the ITEM-INDEX. This index is returned as the second value of ADD-TO-HEAP. Returns the heap.
fibonacci-heap) (item-index node)) ¶Removes an item from the heap, as pointed to by item-index. This
operation is amortised O(1), unless the item removed is the minimum item, in
which case the operation is equivalent to a POP-HEAP.
binary-heap) (item-index integer)) ¶Deltes an item from the heap. ITEM-INDEX is an index representing the value to remove, and is the second value returned from ADD-TO-HEAP. Note that running most HEAP functions can modify which value is pointed to by ITEM-INDEX, so this function is given mostly for completeness. Use a Fibonacci heap if this functionality is important to you. This operation completes in O(log(n)) time, where n is the number of items in the heap.
Removes an element from the front of the queue and returns it. This is an amortised O(log(n)) operation.
Removes all contents from the given heap. Returns the heap.
fibonacci-heap)) ¶Clears all items from the heap. This is a constant time operation.
binary-heap)) ¶Clears the heap. A constant time operation.
Removes all items from the queue. This is a constant time operation.
priority-queue)) ¶Adds an item with a given priority on to the
queue. Returns a list containing first the priority, then the
item. This is a constant time operation.
priority-queue) item priority) ¶Returns the number of elements in the heap.
fibonacci-heap)) ¶binary-heap)) ¶Returns true iff the given heap is empty.
fibonacci-heap)) ¶binary-heap)) ¶Returns a new heap that is the merged copy of those
given here. Can only merge heaps which use the same key and sorting
function. The two arguments are nt modified by this function.
fibonacci-heap) (second fibonacci-heap)) ¶Returns the merge of the two given heaps. This operation runs in O(n + m), where n and m are the number of items in each heap.
binary-heap) (second binary-heap)) ¶Non-destructively merges two BINARY-HEAPs. This is an O(n + m + log(n + m)) operation, n and m being the zies of the two heaps.
Destructively updates the arguments to contain the
merge of both heaps, which is then returned. Can only merge heaps
which use the same key and sorting function.
fibonacci-heap) (second fibonacci-heap)) ¶Destructively marges the two heaps. This is a constant time operation.
binary-heap) (second binary-heap)) ¶Destructively merges two BINARY-HEAPs, and returns the
result. Where n and m are the sizes of each queue, this is an order
O(m + log(n + m) operation, unless an array resize is required, for
which it becomes O(n + m + log(n + m)).
Returns the heap’s root, without modifying the heap. Returns nil if the heap is empty.
fibonacci-heap)) ¶See the heap’s minimum value without modifying the heap. This is a constant time operation.
binary-heap)) ¶Returns the minimum object of the heap, without updating the heap. This is an O(1) operation.
Returns the element at the front of the queue,
without modifying the queue. This is a constant time operation.
priority-queue)) ¶Removes the top element from the heap and returns it.
fibonacci-heap)) ¶Remove the minimum element in the tree. This has an amortised running time of O(log(n)), where n is the number of items in the heap.
binary-heap)) ¶Removes the minimum item from the heap. This is an O(log(n)) operation, where n is the number of items in the heap.
Returns the number of elements in the queue.
priority-queue)) ¶binary-heap) &key size) ¶priority-queue) &key sort-fun) ¶The base condition type for all errors that should generally be thrown in the CL-HEAP package.
error.
(quote "an error has occured while using this data structure.")
:message
This slot is read-only.
(quote "when using decrease-key, the heap-key function should always take two arguments.")
:message
An implementation of a classic binary heap. This uses the standard array-based implementation.
A heap made up of item-disjoint, heap-ordered
trees. Has some good time constraints on various heap operations.
The base type of the two HEAP implementations.
The function used to apply an order to elements in the heap.
(function <)
:sort-fun
This slot is read-only.
A simple priority queue implementaiton, based on a Fibonacci heap.
Compares two items, using the HEAP’s SORT-FUN and KEY functions.
Cuts a child from its parent and makes and places it in the root list.
fibonacci-heap) (node node)) ¶Deletes this node from the linked list that it
represents, and returns the new list. Nulls the node’s parent, and
resets its rank if appropriate.
null)) ¶heap-error)) ¶Places node-two as a child of node-one if node-one’s item is smaller, or vice versa.
fibonacci-heap) (node-one node) (node-two node)) ¶Joins together two fibonacci heaps.
fibonacci-heap) (heap2 fibonacci-heap)) ¶fibonacci-heap) (item node)) ¶Adds a node to the heap.
Used to move a value in the DATA array of a
BINARY-HEAP down the parent-child relationship hierarchy, and so
preserve heap-ordering.
binary-heap) (position integer)) ¶binary-heap) (position integer)) ¶A class used for storing data in a FIBONACCI-HEAP.
concatenate-node-lists.
concatenate-node-lists.
concatenate-node-lists.
cut-node.
decrease-key.
delete-from-heap.
delete-node.
initialize-instance.
is-node-root-p.
link.
mark-node.
meld.
(setf node-child).
node-child.
(setf node-item).
node-item.
(setf node-last).
node-last.
(setf node-marked-p).
node-marked-p.
(setf node-next).
node-next.
(setf node-parent).
node-parent.
(setf node-rank).
node-rank.
print-object.
unmark-node.
:item
The number of children the node has.
0
Used to implement cascading cuts.
common-lisp.
| Jump to: | (
A B C D E F G H I L M N P Q U |
|---|
| Jump to: | (
A B C D E F G H I L M N P Q U |
|---|
| Jump to: | C D E H I K L M N P R S |
|---|
| Jump to: | C D E H I K L M N P R S |
|---|
| Jump to: | B C F H K N P S |
|---|
| Jump to: | B C F H K N P S |
|---|