The cl-heap Reference Manual

This is the cl-heap Reference Manual, version 0.1.6, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sat Dec 03 20:15:25 2022 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 cl-heap

An implementation of heap and priority queue data structures.

Author

Rudy Neeser <>

License

GPLv3

Version

0.1.6

Source

cl-heap.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


3.1 Lisp


3.1.1 cl-heap/cl-heap.asd

Source

cl-heap.asd.

Parent Component

cl-heap (system).

ASDF Systems

cl-heap.

Packages

cl-heap-asdf.


3.1.2 cl-heap/package.lisp

Source

cl-heap.asd.

Parent Component

cl-heap (system).

Packages

cl-heap.


3.1.3 cl-heap/condition.lisp

Dependency

package.lisp (file).

Source

cl-heap.asd.

Parent Component

cl-heap (system).

Public Interface
Internals

heap-error-message (reader method).


3.1.4 cl-heap/heap.lisp

Dependency

condition.lisp (file).

Source

cl-heap.asd.

Parent Component

cl-heap (system).

Public Interface
Internals

compare-items (generic function).


3.1.5 cl-heap/binary-heap.lisp

Dependency

heap.lisp (file).

Source

cl-heap.asd.

Parent Component

cl-heap (system).

Public Interface
Internals

3.1.6 cl-heap/fibonacci-heap.lisp

Dependency

binary-heap.lisp (file).

Source

cl-heap.asd.

Parent Component

cl-heap (system).

Public Interface
Internals

3.1.7 cl-heap/priority-queue.lisp

Dependency

fibonacci-heap.lisp (file).

Source

cl-heap.asd.

Parent Component

cl-heap (system).

Public Interface

4 Packages

Packages are listed by definition order.


4.1 cl-heap-asdf

Source

cl-heap.asd.

Use List
  • asdf/interface.
  • common-lisp.

4.2 cl-heap

An implementation of heap and priority queue data structures.

Source

package.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


5.1 Public Interface


5.1.1 Generic functions

Generic Function: add-all-to-heap (heap items)

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.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: add-all-to-heap ((heap fibonacci-heap) (items list))

Adds the following list of items into the heap. This is an O(n) operation.

Source

fibonacci-heap.lisp.

Method: add-all-to-heap ((heap 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.

Source

binary-heap.lisp.

Generic Function: add-to-heap (heap item)

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.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: add-to-heap ((heap fibonacci-heap) item)

Adds an item to a Fibonacci-heap. This is a constant time operation. Returns the item added to the heap.

Source

fibonacci-heap.lisp.

Method: add-to-heap ((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.

Source

binary-heap.lisp.

Generic Reader: binary-heap-extension-factor (object)
Generic Writer: (setf binary-heap-extension-factor) (object)
Package

cl-heap.

Methods
Reader Method: binary-heap-extension-factor ((binary-heap binary-heap))
Writer Method: (setf binary-heap-extension-factor) ((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.

Source

binary-heap.lisp.

Target Slot

extension-factor.

Generic Function: decrease-key (heap item-index value)

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.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: decrease-key ((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.

Source

fibonacci-heap.lisp.

Method: decrease-key ((heap 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.

Source

binary-heap.lisp.

Generic Function: delete-from-heap (heap item-index)

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.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: delete-from-heap ((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.

Source

fibonacci-heap.lisp.

Method: delete-from-heap ((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.

Source

binary-heap.lisp.

Generic Function: dequeue (queue)

Removes an element from the front of the queue and returns it. This is an amortised O(log(n)) operation.

Package

cl-heap.

Source

priority-queue.lisp.

Methods
Method: dequeue (queue)
Generic Function: empty-heap (heap)

Removes all contents from the given heap. Returns the heap.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: empty-heap ((heap fibonacci-heap))

Clears all items from the heap. This is a constant time operation.

Source

fibonacci-heap.lisp.

Method: empty-heap ((heap binary-heap))

Clears the heap. A constant time operation.

Source

binary-heap.lisp.

Generic Function: empty-queue (queue)

Removes all items from the queue. This is a constant time operation.

Package

cl-heap.

Source

priority-queue.lisp.

Methods
Method: empty-queue ((queue priority-queue))
Generic Function: enqueue (queue item priority)

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.

Package

cl-heap.

Source

priority-queue.lisp.

Methods
Method: enqueue ((queue priority-queue) item priority)
Generic Reader: heap-key (object)
Package

cl-heap.

Methods
Reader Method: heap-key ((heap heap))

A function used to obtain the elements which
should be compared to give an order to the items in the heap.

Source

heap.lisp.

Target Slot

key.

Generic Function: heap-size (heap)

Returns the number of elements in the heap.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: heap-size ((heap fibonacci-heap))
Source

fibonacci-heap.lisp.

Method: heap-size ((heap binary-heap))
Source

binary-heap.lisp.

Generic Reader: heap-sorting-function (object)
Package

cl-heap.

Methods
Reader Method: heap-sorting-function ((heap heap))

The function used to apply an order to elements in the heap.

Source

heap.lisp.

Target Slot

sort-fun.

Generic Function: is-empty-heap-p (heap)

Returns true iff the given heap is empty.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: is-empty-heap-p ((heap fibonacci-heap))
Source

fibonacci-heap.lisp.

Method: is-empty-heap-p ((heap binary-heap))
Source

binary-heap.lisp.

Generic Function: merge-heaps (first second)

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.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: merge-heaps ((first 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.

Source

fibonacci-heap.lisp.

Method: merge-heaps ((first 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.

Source

binary-heap.lisp.

Generic Function: nmerge-heaps (first second)

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.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: nmerge-heaps ((first fibonacci-heap) (second fibonacci-heap))

Destructively marges the two heaps. This is a constant time operation.

Source

fibonacci-heap.lisp.

Method: nmerge-heaps ((first 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)).

Source

binary-heap.lisp.

Generic Function: peep-at-heap (heap)

Returns the heap’s root, without modifying the heap. Returns nil if the heap is empty.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: peep-at-heap ((heap fibonacci-heap))

See the heap’s minimum value without modifying the heap. This is a constant time operation.

Source

fibonacci-heap.lisp.

Method: peep-at-heap ((heap binary-heap))

Returns the minimum object of the heap, without updating the heap. This is an O(1) operation.

Source

binary-heap.lisp.

Generic Function: peep-at-queue (queue)

Returns the element at the front of the queue,
without modifying the queue. This is a constant time operation.

Package

cl-heap.

Source

priority-queue.lisp.

Methods
Method: peep-at-queue ((queue priority-queue))
Generic Function: pop-heap (heap)

Removes the top element from the heap and returns it.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: pop-heap ((heap 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.

Source

fibonacci-heap.lisp.

Method: pop-heap ((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.

Source

binary-heap.lisp.

Generic Function: queue-size (queue)

Returns the number of elements in the queue.

Package

cl-heap.

Source

priority-queue.lisp.

Methods
Method: queue-size ((queue priority-queue))

5.1.2 Standalone methods

Method: initialize-instance :after ((queue priority-queue) &key sort-fun)
Source

priority-queue.lisp.

Method: initialize-instance :after ((heap binary-heap) &key size)
Source

binary-heap.lisp.

Method: initialize-instance :after ((node node) &key)
Source

fibonacci-heap.lisp.

Method: print-object ((heap heap) stream)
Source

heap.lisp.

Method: print-object ((node node) stream)
Source

fibonacci-heap.lisp.


5.1.3 Conditions

Condition: heap-error

The base condition type for all errors that should generally be thrown in the CL-HEAP package.

Package

cl-heap.

Source

condition.lisp.

Direct superclasses

error.

Direct subclasses

key-error.

Direct methods

heap-error-message.

Direct slots
Slot: message
Initform

(quote "an error has occured while using this data structure.")

Initargs

:message

Readers

heap-error-message.

Writers

This slot is read-only.

Condition: key-error
Package

cl-heap.

Source

condition.lisp.

Direct superclasses

heap-error.

Direct slots
Slot: message
Initform

(quote "when using decrease-key, the heap-key function should always take two arguments.")

Initargs

:message


5.1.4 Classes

Class: binary-heap

An implementation of a classic binary heap. This uses the standard array-based implementation.

Package

cl-heap.

Source

binary-heap.lisp.

Direct superclasses

heap.

Direct methods
Direct slots
Slot: data

The heap’s stored data.

Slot: extension-factor

The percentage at which the space
allocated for data in the heap should grow at once that space has been exceeded.

Initform

50

Readers

binary-heap-extension-factor.

Writers

(setf binary-heap-extension-factor).

Class: fibonacci-heap

A heap made up of item-disjoint, heap-ordered
trees. Has some good time constraints on various heap operations.

Package

cl-heap.

Source

fibonacci-heap.lisp.

Direct superclasses

heap.

Direct methods
Direct slots
Slot: root

The minimum element in the tree.

Slot: count

The number of items in the heap.

Package

common-lisp.

Initform

0

Class: heap

The base type of the two HEAP implementations.

Package

cl-heap.

Source

heap.lisp.

Direct subclasses
Direct methods
Direct slots
Slot: sort-fun

The function used to apply an order to elements in the heap.

Initform

(function <)

Initargs

:sort-fun

Readers

heap-sorting-function.

Writers

This slot is read-only.

Slot: key

A function used to obtain the elements which
should be compared to give an order to the items in the heap.

Initform

(function identity)

Initargs

:key

Readers

heap-key.

Writers

This slot is read-only.

Class: priority-queue

A simple priority queue implementaiton, based on a Fibonacci heap.

Package

cl-heap.

Source

priority-queue.lisp.

Direct methods
Direct slots
Slot: heap

5.2 Internals


5.2.1 Macros

Macro: do-each-node ((symbol node) &body body)
Package

cl-heap.

Source

fibonacci-heap.lisp.


5.2.2 Ordinary functions

Function: children-positions (position)
Package

cl-heap.

Source

binary-heap.lisp.

Function: parent-position (position)
Package

cl-heap.

Source

binary-heap.lisp.


5.2.3 Generic functions

Generic Function: compare-items (heap parent child)

Compares two items, using the HEAP’s SORT-FUN and KEY functions.

Package

cl-heap.

Source

heap.lisp.

Methods
Method: compare-items ((heap heap) parent child)
Generic Function: concatenate-node-lists (lhs rhs)
Package

cl-heap.

Source

fibonacci-heap.lisp.

Methods
Method: concatenate-node-lists ((lhs node) (rhs null))
Method: concatenate-node-lists ((lhs null) (rhs node))
Method: concatenate-node-lists ((lhs node) (rhs node))
Generic Function: cut-node (heap node)

Cuts a child from its parent and makes and places it in the root list.

Package

cl-heap.

Source

fibonacci-heap.lisp.

Methods
Method: cut-node ((heap fibonacci-heap) (node node))
Generic Function: delete-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.

Package

cl-heap.

Source

fibonacci-heap.lisp.

Methods
Method: delete-node ((node null))
Method: delete-node ((node node))
Generic Reader: heap-error-message (condition)
Package

cl-heap.

Methods
Reader Method: heap-error-message ((condition heap-error))
Source

condition.lisp.

Target Slot

message.

Generic Function: is-node-root-p (node)
Package

cl-heap.

Source

fibonacci-heap.lisp.

Methods
Method: is-node-root-p ((node node))

Places node-two as a child of node-one if node-one’s item is smaller, or vice versa.

Package

cl-heap.

Source

fibonacci-heap.lisp.

Methods
Generic Function: mark-node (node)
Package

cl-heap.

Source

fibonacci-heap.lisp.

Methods
Method: mark-node ((node node))
Generic Function: meld (one two)

Joins together two fibonacci heaps.

Package

cl-heap.

Source

fibonacci-heap.lisp.

Methods
Method: meld ((heap1 fibonacci-heap) (heap2 fibonacci-heap))
Method: meld ((heap fibonacci-heap) (item node))

Adds a node to the heap.

Generic Reader: node-child (object)
Package

cl-heap.

Methods
Reader Method: node-child ((node node))

automatically generated reader method

Source

fibonacci-heap.lisp.

Target Slot

child.

Generic Writer: (setf node-child) (object)
Package

cl-heap.

Methods
Writer Method: (setf node-child) ((node node))

automatically generated writer method

Source

fibonacci-heap.lisp.

Target Slot

child.

Generic Reader: node-item (object)
Package

cl-heap.

Methods
Reader Method: node-item ((node node))

automatically generated reader method

Source

fibonacci-heap.lisp.

Target Slot

item.

Generic Writer: (setf node-item) (object)
Package

cl-heap.

Methods
Writer Method: (setf node-item) ((node node))

automatically generated writer method

Source

fibonacci-heap.lisp.

Target Slot

item.

Generic Reader: node-last (object)
Package

cl-heap.

Methods
Reader Method: node-last ((node node))

automatically generated reader method

Source

fibonacci-heap.lisp.

Target Slot

last.

Generic Writer: (setf node-last) (object)
Package

cl-heap.

Methods
Writer Method: (setf node-last) ((node node))

automatically generated writer method

Source

fibonacci-heap.lisp.

Target Slot

last.

Generic Reader: node-marked-p (object)
Generic Writer: (setf node-marked-p) (object)
Package

cl-heap.

Methods
Reader Method: node-marked-p ((node node))
Writer Method: (setf node-marked-p) ((node node))

Used to implement cascading cuts.

Source

fibonacci-heap.lisp.

Target Slot

marked.

Generic Reader: node-next (object)
Package

cl-heap.

Methods
Reader Method: node-next ((node node))

automatically generated reader method

Source

fibonacci-heap.lisp.

Target Slot

next.

Generic Writer: (setf node-next) (object)
Package

cl-heap.

Methods
Writer Method: (setf node-next) ((node node))

automatically generated writer method

Source

fibonacci-heap.lisp.

Target Slot

next.

Generic Reader: node-parent (object)
Package

cl-heap.

Methods
Reader Method: node-parent ((node node))

automatically generated reader method

Source

fibonacci-heap.lisp.

Target Slot

parent.

Generic Writer: (setf node-parent) (object)
Package

cl-heap.

Methods
Writer Method: (setf node-parent) ((node node))

automatically generated writer method

Source

fibonacci-heap.lisp.

Target Slot

parent.

Generic Reader: node-rank (object)
Generic Writer: (setf node-rank) (object)
Package

cl-heap.

Methods
Reader Method: node-rank ((node node))
Writer Method: (setf node-rank) ((node node))

The number of children the node has.

Source

fibonacci-heap.lisp.

Target Slot

rank.

Generic Function: percolate-down (heap position)

Used to move a value in the DATA array of a
BINARY-HEAP down the parent-child relationship hierarchy, and so preserve heap-ordering.

Package

cl-heap.

Source

binary-heap.lisp.

Methods
Method: percolate-down ((heap binary-heap) (position integer))
Generic Function: percolate-up (heap position)
Package

cl-heap.

Source

binary-heap.lisp.

Methods
Method: percolate-up ((heap binary-heap) (position integer))
Generic Function: unmark-node (node)
Package

cl-heap.

Source

fibonacci-heap.lisp.

Methods
Method: unmark-node ((node node))

5.2.4 Classes

Class: node

A class used for storing data in a FIBONACCI-HEAP.

Package

cl-heap.

Source

fibonacci-heap.lisp.

Direct methods
Direct slots
Slot: item
Initargs

:item

Readers

node-item.

Writers

(setf node-item).

Slot: parent
Readers

node-parent.

Writers

(setf node-parent).

Slot: child
Readers

node-child.

Writers

(setf node-child).

Slot: rank

The number of children the node has.

Initform

0

Readers

node-rank.

Writers

(setf node-rank).

Slot: marked

Used to implement cascading cuts.

Readers

node-marked-p.

Writers

(setf node-marked-p).

Slot: next
Readers

node-next.

Writers

(setf node-next).

Slot: last
Package

common-lisp.

Readers

node-last.

Writers

(setf node-last).


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   (  
A   B   C   D   E   F   G   H   I   L   M   N   P   Q   U  
Index Entry  Section

(
(setf binary-heap-extension-factor): Public generic functions
(setf binary-heap-extension-factor): Public generic functions
(setf node-child): Private generic functions
(setf node-child): Private generic functions
(setf node-item): Private generic functions
(setf node-item): Private generic functions
(setf node-last): Private generic functions
(setf node-last): Private generic functions
(setf node-marked-p): Private generic functions
(setf node-marked-p): Private generic functions
(setf node-next): Private generic functions
(setf node-next): Private generic functions
(setf node-parent): Private generic functions
(setf node-parent): Private generic functions
(setf node-rank): Private generic functions
(setf node-rank): Private generic functions

A
add-all-to-heap: Public generic functions
add-all-to-heap: Public generic functions
add-all-to-heap: Public generic functions
add-to-heap: Public generic functions
add-to-heap: Public generic functions
add-to-heap: Public generic functions

B
binary-heap-extension-factor: Public generic functions
binary-heap-extension-factor: Public generic functions

C
children-positions: Private ordinary functions
compare-items: Private generic functions
compare-items: Private generic functions
concatenate-node-lists: Private generic functions
concatenate-node-lists: Private generic functions
concatenate-node-lists: Private generic functions
concatenate-node-lists: Private generic functions
cut-node: Private generic functions
cut-node: Private generic functions

D
decrease-key: Public generic functions
decrease-key: Public generic functions
decrease-key: Public generic functions
delete-from-heap: Public generic functions
delete-from-heap: Public generic functions
delete-from-heap: Public generic functions
delete-node: Private generic functions
delete-node: Private generic functions
delete-node: Private generic functions
dequeue: Public generic functions
dequeue: Public generic functions
do-each-node: Private macros

E
empty-heap: Public generic functions
empty-heap: Public generic functions
empty-heap: Public generic functions
empty-queue: Public generic functions
empty-queue: Public generic functions
enqueue: Public generic functions
enqueue: Public generic functions

F
Function, children-positions: Private ordinary functions
Function, parent-position: Private ordinary functions

G
Generic Function, (setf binary-heap-extension-factor): Public generic functions
Generic Function, (setf node-child): Private generic functions
Generic Function, (setf node-item): Private generic functions
Generic Function, (setf node-last): Private generic functions
Generic Function, (setf node-marked-p): Private generic functions
Generic Function, (setf node-next): Private generic functions
Generic Function, (setf node-parent): Private generic functions
Generic Function, (setf node-rank): Private generic functions
Generic Function, add-all-to-heap: Public generic functions
Generic Function, add-to-heap: Public generic functions
Generic Function, binary-heap-extension-factor: Public generic functions
Generic Function, compare-items: Private generic functions
Generic Function, concatenate-node-lists: Private generic functions
Generic Function, cut-node: Private generic functions
Generic Function, decrease-key: Public generic functions
Generic Function, delete-from-heap: Public generic functions
Generic Function, delete-node: Private generic functions
Generic Function, dequeue: Public generic functions
Generic Function, empty-heap: Public generic functions
Generic Function, empty-queue: Public generic functions
Generic Function, enqueue: Public generic functions
Generic Function, heap-error-message: Private generic functions
Generic Function, heap-key: Public generic functions
Generic Function, heap-size: Public generic functions
Generic Function, heap-sorting-function: Public generic functions
Generic Function, is-empty-heap-p: Public generic functions
Generic Function, is-node-root-p: Private generic functions
Generic Function, link: Private generic functions
Generic Function, mark-node: Private generic functions
Generic Function, meld: Private generic functions
Generic Function, merge-heaps: Public generic functions
Generic Function, nmerge-heaps: Public generic functions
Generic Function, node-child: Private generic functions
Generic Function, node-item: Private generic functions
Generic Function, node-last: Private generic functions
Generic Function, node-marked-p: Private generic functions
Generic Function, node-next: Private generic functions
Generic Function, node-parent: Private generic functions
Generic Function, node-rank: Private generic functions
Generic Function, peep-at-heap: Public generic functions
Generic Function, peep-at-queue: Public generic functions
Generic Function, percolate-down: Private generic functions
Generic Function, percolate-up: Private generic functions
Generic Function, pop-heap: Public generic functions
Generic Function, queue-size: Public generic functions
Generic Function, unmark-node: Private generic functions

H
heap-error-message: Private generic functions
heap-error-message: Private generic functions
heap-key: Public generic functions
heap-key: Public generic functions
heap-size: Public generic functions
heap-size: Public generic functions
heap-size: Public generic functions
heap-sorting-function: Public generic functions
heap-sorting-function: Public generic functions

I
initialize-instance: Public standalone methods
initialize-instance: Public standalone methods
initialize-instance: Public standalone methods
is-empty-heap-p: Public generic functions
is-empty-heap-p: Public generic functions
is-empty-heap-p: Public generic functions
is-node-root-p: Private generic functions
is-node-root-p: Private generic functions

L
link: Private generic functions
link: Private generic functions

M
Macro, do-each-node: Private macros
mark-node: Private generic functions
mark-node: Private generic functions
meld: Private generic functions
meld: Private generic functions
meld: Private generic functions
merge-heaps: Public generic functions
merge-heaps: Public generic functions
merge-heaps: Public generic functions
Method, (setf binary-heap-extension-factor): Public generic functions
Method, (setf node-child): Private generic functions
Method, (setf node-item): Private generic functions
Method, (setf node-last): Private generic functions
Method, (setf node-marked-p): Private generic functions
Method, (setf node-next): Private generic functions
Method, (setf node-parent): Private generic functions
Method, (setf node-rank): Private generic functions
Method, add-all-to-heap: Public generic functions
Method, add-all-to-heap: Public generic functions
Method, add-to-heap: Public generic functions
Method, add-to-heap: Public generic functions
Method, binary-heap-extension-factor: Public generic functions
Method, compare-items: Private generic functions
Method, concatenate-node-lists: Private generic functions
Method, concatenate-node-lists: Private generic functions
Method, concatenate-node-lists: Private generic functions
Method, cut-node: Private generic functions
Method, decrease-key: Public generic functions
Method, decrease-key: Public generic functions
Method, delete-from-heap: Public generic functions
Method, delete-from-heap: Public generic functions
Method, delete-node: Private generic functions
Method, delete-node: Private generic functions
Method, dequeue: Public generic functions
Method, empty-heap: Public generic functions
Method, empty-heap: Public generic functions
Method, empty-queue: Public generic functions
Method, enqueue: Public generic functions
Method, heap-error-message: Private generic functions
Method, heap-key: Public generic functions
Method, heap-size: Public generic functions
Method, heap-size: Public generic functions
Method, heap-sorting-function: Public generic functions
Method, initialize-instance: Public standalone methods
Method, initialize-instance: Public standalone methods
Method, initialize-instance: Public standalone methods
Method, is-empty-heap-p: Public generic functions
Method, is-empty-heap-p: Public generic functions
Method, is-node-root-p: Private generic functions
Method, link: Private generic functions
Method, mark-node: Private generic functions
Method, meld: Private generic functions
Method, meld: Private generic functions
Method, merge-heaps: Public generic functions
Method, merge-heaps: Public generic functions
Method, nmerge-heaps: Public generic functions
Method, nmerge-heaps: Public generic functions
Method, node-child: Private generic functions
Method, node-item: Private generic functions
Method, node-last: Private generic functions
Method, node-marked-p: Private generic functions
Method, node-next: Private generic functions
Method, node-parent: Private generic functions
Method, node-rank: Private generic functions
Method, peep-at-heap: Public generic functions
Method, peep-at-heap: Public generic functions
Method, peep-at-queue: Public generic functions
Method, percolate-down: Private generic functions
Method, percolate-up: Private generic functions
Method, pop-heap: Public generic functions
Method, pop-heap: Public generic functions
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods
Method, queue-size: Public generic functions
Method, unmark-node: Private generic functions

N
nmerge-heaps: Public generic functions
nmerge-heaps: Public generic functions
nmerge-heaps: Public generic functions
node-child: Private generic functions
node-child: Private generic functions
node-item: Private generic functions
node-item: Private generic functions
node-last: Private generic functions
node-last: Private generic functions
node-marked-p: Private generic functions
node-marked-p: Private generic functions
node-next: Private generic functions
node-next: Private generic functions
node-parent: Private generic functions
node-parent: Private generic functions
node-rank: Private generic functions
node-rank: Private generic functions

P
parent-position: Private ordinary functions
peep-at-heap: Public generic functions
peep-at-heap: Public generic functions
peep-at-heap: Public generic functions
peep-at-queue: Public generic functions
peep-at-queue: Public generic functions
percolate-down: Private generic functions
percolate-down: Private generic functions
percolate-up: Private generic functions
percolate-up: Private generic functions
pop-heap: Public generic functions
pop-heap: Public generic functions
pop-heap: Public generic functions
print-object: Public standalone methods
print-object: Public standalone methods

Q
queue-size: Public generic functions
queue-size: Public generic functions

U
unmark-node: Private generic functions
unmark-node: Private generic functions


A.4 Data types

Jump to:   B   C   F   H   K   N   P   S  
Index Entry  Section

B
binary-heap: Public classes
binary-heap.lisp: The cl-heap/binary-heap․lisp file

C
cl-heap: The cl-heap system
cl-heap: The cl-heap package
cl-heap-asdf: The cl-heap-asdf package
cl-heap.asd: The cl-heap/cl-heap․asd file
Class, binary-heap: Public classes
Class, fibonacci-heap: Public classes
Class, heap: Public classes
Class, node: Private classes
Class, priority-queue: Public classes
Condition, heap-error: Public conditions
Condition, key-error: Public conditions
condition.lisp: The cl-heap/condition․lisp file

F
fibonacci-heap: Public classes
fibonacci-heap.lisp: The cl-heap/fibonacci-heap․lisp file
File, binary-heap.lisp: The cl-heap/binary-heap․lisp file
File, cl-heap.asd: The cl-heap/cl-heap․asd file
File, condition.lisp: The cl-heap/condition․lisp file
File, fibonacci-heap.lisp: The cl-heap/fibonacci-heap․lisp file
File, heap.lisp: The cl-heap/heap․lisp file
File, package.lisp: The cl-heap/package․lisp file
File, priority-queue.lisp: The cl-heap/priority-queue․lisp file

H
heap: Public classes
heap-error: Public conditions
heap.lisp: The cl-heap/heap․lisp file

K
key-error: Public conditions

N
node: Private classes

P
Package, cl-heap: The cl-heap package
Package, cl-heap-asdf: The cl-heap-asdf package
package.lisp: The cl-heap/package․lisp file
priority-queue: Public classes
priority-queue.lisp: The cl-heap/priority-queue․lisp file

S
System, cl-heap: The cl-heap system