The cl-heap Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The cl-heap Reference Manual

This is the cl-heap Reference Manual, version 0.1.6, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 11:10:29 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

CL-HEAP

CL-HEAP is a Common Lisp library that provides efficient priority queue and heap implementations. Heaps are tree data structure in which any child, c, of a parent, p, obeys the relation p R c, for some relation R (often less-than or greater-than). Heaps can be used directly as priority queues, and are important components of many algorithms, like those for finding shortest paths and calculating minimum spanning trees.

The library is simple to use. Here's an example covering most of the priority queue functionality:

(defparameter *queue* (make-instance 'cl-heap:priority-queue))

(cl-heap:enqueue *queue* 'test 15) ; Enqueue the item with the priority of 15.
(cl-heap:enqueue *queue* 'this -5)
(cl-heap:enqueue *queue* 'a 10)
(cl-heap:enqueue *queue* 'is 5)

(cl-heap:peep-at-queue *queue*) => 'this

(cl-heap:dequeue *queue*) => 'this
(cl-heap:dequeue *queue*) => 'is
(cl-heap:dequeue *queue*) => 'a
(cl-heap:dequeue *queue*) => 'test

The library provides an implementation of an array-based binary heap - offering O(log(n)) times for most operations - and the Fibonacci heap. While any sequence of arbitrary operations on a Fibonacci heap occur in amortised logarithmic time, many common operations occur in constant and amortised constant time. See below for further details. The Fibonacci heap should generally be your heap of choice from this library.

Installation and Usage

CL-HEAP depends on XLUNIT, which is used to perform unit testing. CL-HEAP has been tested and is known to run on SBCL. If you've tried this on other compilers and it runs successfully, please let me know. The library can be installed using either ASDF-INSTALL or QUICKLISP:

(require 'asdf-install)
(asdf-install:install 'cl-heap)

(quicklisp:quickload 'cl-heap)
(quicklisp:quickload 'cl-heap-tests) 

After which, the library can then be loaded using either ASDF or QUICKLISP:

(asdf:load-system 'cl-heap)

Test Suite

CL-HEAP comes with a test suite. The tests for the various classes can be performed as follows:

(xlunit:textui-test-run (xlunit:get-suite cl-heap:fibonacci-test))
(xlunit:textui-test-run (xlunit:get-suite cl-heap:binary-test))
(xlunit:textui-test-run (xlunit:get-suite cl-heap:priority-queue-test))

The PRIORITY-QUEUE Class

This priority queue is a container for items in which all the items are sorted by some given priority. We implement the priority queue using a Fibonacci heap.

MAKE-INSTANCE accepts the argument :sort-fun to provide the function which the items' priorities are sorted by. This defaults to #'<, which will cause the queue to always return the item of lowest priority.

(ENQUEUE queue item priority)

Adds the item to the queue at the given priority. Returns a list containing first the item's priority, then the item itself. Running time: O(1)

(DEQUEUE queue)

Removes the item of lowest priority from the queue. Running time: amortised O(log(n))

(PEEP-AT-QUEUE queue)

Returns the item of lowest priority from the queue, without modifying the queue. Running time: O(1)

(EMPTY-QUEUE queue)

Removes all items from the queue. Returns the heap. Running time: O(1)

(QUEUE-SIZE queue)

Returns the number of items in the queue. Running time: O(1)

The HEAP Class

HEAP provides functionality common to the two heap classes implement by CL-HEAP. Each heap implementation accepts at least two arguments to MAKE-INSTANCE: :key and :sort-fun. :sort-fun supplies the function to be used when comparing two objects to each other, and defaults to #'<. :key gives a function which should be first applied to the elements in the HEAP before comparing them using the sorting function. :key defaults to #'identity. These functions can be accessed using HEAP-KEY and HEAP-SORTING-FUNCTION.

Both of the heap implementations obey the same interface:

(HEAP-KEY heap)

Returns the function passed as the :key argument to the heap.

(HEAP-SORTING-FUNCTION heap)

Returns the function used to sort the elements in the heap.

(HEAP-SIZE heap)

Returns the number of elements in the heap.

(EMPTY-HEAP heap)

Removes all items from the heap, and returns the heap.

(IS-EMPTY-HEAP-P heap)

Returns true iff the heap contains no elements.

(ADD-TO-HEAP heap item)

Adds the given item to the heap. Returns two values: first the item itself, and then some index-key which can be used by DECREASE-KEY and DELETE-KEY to identify which values should be affected by these operations. See below for an example.

(ADD-ALL-TO-HEAP heap items)

Adds all items in the list to the heap, as if by repeated calls to ADD-TO-HEAP. ADD-ALL-TO-HEAP can often be implemented more efficiently, though, than by merely executing consecutive calls to ADD-TO-HEAP directly. Returns the heap object.

(PEEP-AT-HEAP heap)

Returns the minimum item in the heap, without modifying the heap.

(POP-HEAP heap)

Removes the smallest item in the heap, and returns it.

(MERGE-HEAPS first second)

Returns a new heap which contains all the items in both heaps. Only heaps which use the same HEAP-KEY and HEAP-SORTING-FUNCTION can be merged, otherwise a HEAP-ERROR is signalled.

(NMERGE-HEAPS first second)

Destructively creates a new heap which contains the items in both heaps. Only heaps which use the same HEAP-KEY and HEAP-SORTING-FUNCTION can be merged, otherwise a HEAP-ERROR is signalled.

(DECREASE-KEY heap item-index value)

Allows you to specify an item in the heap whose value should be decreased. ITEM-INDEX is the second value returned by ADD-TO-HEAP, and VALUE should be smaller than the items current value, or a KEY-ERROR will be signalled. Returns the heap. See below for an example.

(DELETE-FROM-HEAP heap item-index)

Allows you to specify an arbitrary item to remove from the heap. ITEM-INDEX is the second value returned by ADD-TO-HEAP.

DECREASE-KEY requires that HEAP-KEY is either the function IDENTITY, or a function that accepts an optional second argument, which will be the value of the new key. For instance, if the elements in the heap are lists, and they are to be sorted by the first element in the list, an appropriate HEAP-KEY could be:

(lambda (item &optional new-value)
    (if new-value
        (setf (first item) new-value)
	(first item)))

Of course, if DECREASE-KEY is not going to be used, then #'first itself could simply be used as the HEAP-KEY.

The BINARY-HEAP Class

BINARY-HEAP is constructed in the typical fashion, using an array. The BINARY-HEAP MAKE-INSTANCE call accepts an extra argument, :size, which sets the data array's initial size.

Note that DECREASE-KEY and DELETE-FROM-HEAP are not very useful operations on this heap: while they work, the required index-keys may be invalidated as soon as any heap operation is performed. If you do want to make use of DELETE-FROM-HEAP or DECREASE-KEY, consider using FIBONACCI-HEAP instead.

BINARY-HEAP provides an extra function to the above API:

(BINARY-HEAP-EXTENSION-FACTOR heap)

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

Here are the Big-Oh running times for the heap API, where n and m are the sizes of various heaps.

(HEAP-SIZE heap)    	    	      => O(1)

(EMPTY-HEAP heap)		      => O(1)

(IS-EMPTY-HEAP-P heap)		      => O(1)

(ADD-TO-HEAP heap item)		      => O(log(n))

(ADD-ALL-TO-HEAP heap items)	      => O(n)

(PEEP-AT-HEAP heap)   		      => O(1)

(POP-HEAP heap)			      => O(log(n))

(MERGE-HEAPS first second)	      => O(n + m + log(n + m))

(NMERGE-HEAPS first second)	      => O(m + log(n + m))

(DECREASE-KEY heap item-index value)  => O(log(n))

(DELETE-FROM-HEAP heap item-index)    => O(log(n))

The FIBONACCI-HEAP Class

The details of the Fibonacci heap are given in "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms", by Fredman and Tarjan (see references below).

The Fibonacci heap has some interesting time constraints, and should generally be used instead of BINARY-HEAP.

Here are the Big-Oh running times for the heap API, where n and m are the sizes of various heaps.

(HEAP-SIZE heap)    	    	      => O(1)

(EMPTY-HEAP heap)		      => O(1)

(IS-EMPTY-HEAP-P heap)		      => O(1)

(ADD-TO-HEAP heap item)		      => O(1)

(ADD-ALL-TO-HEAP heap items)	      => O(n)

(PEEP-AT-HEAP heap)   		      => O(1)

(POP-HEAP heap)			      => amortised O(log(n))

(MERGE-HEAPS first second)	      => O(m + n)

(NMERGE-HEAPS first second)	      => O(1)

(DECREASE-KEY heap item-index value)  => amortised O(1)

(DELETE-FROM-HEAP heap item-index)    => amortised O(1), except where
		       		         the deleted item was the minimum
		       		         item, in which case it is
				         amortised O(log(n))

Examples of Use

A heap can be created quite simply:

(defparameter *heap* (make-instance 'cl-heap:fibonacci-heap))

This will create a heap where the elements are ordered using #'<. Elements can be added one at a time using ADD-TO-HEAP:

(cl-heap:add-to-heap *heap* 1)

or, in a batch.

(cl-heap:add-all-to-heap *heap* '(6 4 7 3 2 0))

The minimum item in this heap can easily by seen using PEEP-AT-HEEP, which will not modify the heap in any way:

(cl-heap:peep-at-heap *heap*) => 0

The minimum item can be removed from the heap using POP-HEAP:

(cl-heap:pop-heap *heap*) => 0

Heaps can be used to sort items:

(let ((heap (make-instance 'cl-heap:fibonacci-heap)))
  (cl-heap:add-all-to-heap heap (loop for i from 1 upto 10 collect (random 100)))
  (loop while (not (cl-heap:is-empty-heap-p heap)) collect (cl-heap:pop-heap heap)))

=> (14 19 30 32 38 64 74 90 96 98)

A max-heap can be constructed as follows:

(defparameter *heap* (make-instance 'cl-heap:fibonacci-heap :sort-fun #'>))

And this will order things from most to least:

(let ((heap (make-instance 'cl-heap:fibonacci-heap :sort-fun #'>)))
  (cl-heap:add-all-to-heap heap (loop for i from 1 upto 10 collect (random 100)))
  (loop while (not (cl-heap:is-empty-heap-p heap)) collect (cl-heap:pop-heap heap)))

=> (69 68 64 60 37 34 30 7 6 1)

The heaps can contain arbitrary items. For instance, a heap whose elements are all lists can be constructed as follows:

(defparameter *heap* (make-instance 'cl-heap:fibonacci-heap :key #'first))
(cl-heap:add-to-heap *heap* (list 5 'some 'arbitrary 'data))
(cl-heap:add-to-heap *heap* (list 4 'other 'data))
(cl-heap:pop-heap *heap*) => (4 other data)

DECREASE-KEY and DELETE-FROM-HEAP can be used as follows:

(defparameter *heap* (make-instance 'cl-heap:fibonacci-heap))
(cl-heap:add-all-to-heap *heap* '(5 3 4 2 1))
(let ((item-index (second (multiple-value-list (cl-heap:add-to-heap *heap* 10)))))
     (format t "Smallest item: ~A~%" (cl-heap:peep-at-heap *heap*))
     (cl-heap:decrease-key *heap* item-index 0)
     (format t "Smallest item: ~A~%" (cl-heap:peep-at-heap *heap*)))

=> nil     
Smallest item: 1
Smallest item: 0

License

CL-HEAP is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

References

M. L. Fredman and R. E. Tarjan. 1987. "Fibonacci Heaps and Their Uses in Improved Network Optimizxation Algorithms". Journal of the Association for Computing Machinery, Vol 34, No 3. pp 596 - 615


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

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


Previous: , Up: Systems   [Contents][Index]

2.1 cl-heap

Author

Rudy Neeser <rudy.neeser@gmail.com>

License

GPLv3

Description

An implementation of heap and priority queue data structures.

Version

0.1.6

Source

cl-heap.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

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


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 cl-heap.asd

Location

cl-heap.asd

Systems

cl-heap (system)

Packages

cl-heap-asdf


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 cl-heap/package.lisp

Parent

cl-heap (system)

Location

package.lisp

Packages

cl-heap


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.3 cl-heap/condition.lisp

Dependency

package.lisp (file)

Parent

cl-heap (system)

Location

condition.lisp

Exported Definitions
Internal Definitions

heap-error-message (method)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.4 cl-heap/heap.lisp

Dependency

condition.lisp (file)

Parent

cl-heap (system)

Location

heap.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.5 cl-heap/binary-heap.lisp

Dependency

heap.lisp (file)

Parent

cl-heap (system)

Location

binary-heap.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.6 cl-heap/fibonacci-heap.lisp

Dependency

binary-heap.lisp (file)

Parent

cl-heap (system)

Location

fibonacci-heap.lisp

Exported Definitions
Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

3.1.7 cl-heap/priority-queue.lisp

Dependency

fibonacci-heap.lisp (file)

Parent

cl-heap (system)

Location

priority-queue.lisp

Exported Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

4.1 cl-heap-asdf

Source

cl-heap.asd

Use List

Previous: , Up: Packages   [Contents][Index]

4.2 cl-heap

An implementation of heap and priority queue data structures.

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

Generic Function: binary-heap-extension-factor OBJECT
Generic Function: (setf binary-heap-extension-factor) NEW-VALUE OBJECT
Package

cl-heap

Methods
Method: binary-heap-extension-factor (BINARY-HEAP binary-heap)
Method: (setf binary-heap-extension-factor) NEW-VALUE (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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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

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

Source

fibonacci-heap.lisp (file)

Method: empty-heap (HEAP binary-heap)

Clears the heap. A constant time operation.

Source

binary-heap.lisp (file)

Generic Function: empty-queue QUEUE

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

Package

cl-heap

Source

priority-queue.lisp (file)

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 (file)

Methods
Method: enqueue (QUEUE priority-queue) ITEM PRIORITY
Generic Function: heap-key OBJECT
Package

cl-heap

Methods
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 (file)

Generic Function: heap-size HEAP

Returns the number of elements in the heap.

Package

cl-heap

Source

heap.lisp (file)

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

fibonacci-heap.lisp (file)

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

binary-heap.lisp (file)

Generic Function: heap-sorting-function OBJECT
Package

cl-heap

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

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

Source

heap.lisp (file)

Generic Function: is-empty-heap-p HEAP

Returns true iff the given heap is empty.

Package

cl-heap

Source

heap.lisp (file)

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

fibonacci-heap.lisp (file)

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

binary-heap.lisp (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

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 (file)

Generic Function: queue-size QUEUE

Returns the number of elements in the queue.

Package

cl-heap

Source

priority-queue.lisp (file)

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

Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 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 (file)

Direct superclasses

error (condition)

Direct subclasses

key-error (condition)

Direct methods

heap-error-message (method)

Direct slots
Slot: message
Initargs

:message

Initform

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

Readers

heap-error-message (generic function)

Condition: key-error ()
Package

cl-heap

Source

condition.lisp (file)

Direct superclasses

heap-error (condition)

Direct slots
Slot: message
Initargs

:message

Initform

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


Previous: , Up: Exported definitions   [Contents][Index]

5.1.3 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 (file)

Direct superclasses

heap (class)

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 (generic function)

Writers

(setf binary-heap-extension-factor) (generic function)

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 (file)

Direct superclasses

heap (class)

Direct methods
Direct slots
Slot: root

The minimum element in the tree.

Slot: count

The number of items in the heap.

Initform

0

Class: heap ()

The base type of the two HEAP implementations.

Package

cl-heap

Source

heap.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses
Direct methods
Direct slots
Slot: sort-fun

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

Initargs

:sort-fun

Initform

(function <)

Readers

heap-sorting-function (generic function)

Slot: key

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

Initargs

:key

Initform

(function identity)

Readers

heap-key (generic function)

Class: priority-queue ()

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

Package

cl-heap

Source

priority-queue.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: heap

Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Macros

Macro: do-each-node (SYMBOL NODE) &body BODY
Package

cl-heap

Source

fibonacci-heap.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Functions

Function: children-positions POSITION
Package

cl-heap

Source

binary-heap.lisp (file)

Function: parent-position POSITION
Package

cl-heap

Source

binary-heap.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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 (file)

Methods
Method: compare-items (HEAP heap) PARENT CHILD
Generic Function: concatenate-node-lists LHS RHS
Package

cl-heap

Source

fibonacci-heap.lisp (file)

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 (file)

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 (file)

Methods
Method: delete-node (NODE null)
Method: delete-node (NODE node)
Generic Function: heap-error-message CONDITION
Package

cl-heap

Methods
Method: heap-error-message (CONDITION heap-error)
Source

condition.lisp (file)

Generic Function: is-node-root-p NODE
Package

cl-heap

Source

fibonacci-heap.lisp (file)

Methods
Method: is-node-root-p (NODE node)
Generic Function: link HEAP NODE-ONE NODE-TWO

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 (file)

Methods
Method: link (HEAP fibonacci-heap) (NODE-ONE node) (NODE-TWO node)
Generic Function: mark-node NODE
Package

cl-heap

Source

fibonacci-heap.lisp (file)

Methods
Method: mark-node (NODE node)
Generic Function: meld ONE TWO

Joins together two fibonacci heaps.

Package

cl-heap

Source

fibonacci-heap.lisp (file)

Methods
Method: meld (HEAP1 fibonacci-heap) (HEAP2 fibonacci-heap)
Method: meld (HEAP fibonacci-heap) (ITEM node)

Adds a node to the heap.

Generic Function: node-child OBJECT
Generic Function: (setf node-child) NEW-VALUE OBJECT
Package

cl-heap

Methods
Method: node-child (NODE node)

automatically generated reader method

Source

fibonacci-heap.lisp (file)

Method: (setf node-child) NEW-VALUE (NODE node)

automatically generated writer method

Source

fibonacci-heap.lisp (file)

Generic Function: node-item OBJECT
Generic Function: (setf node-item) NEW-VALUE OBJECT
Package

cl-heap

Methods
Method: node-item (NODE node)

automatically generated reader method

Source

fibonacci-heap.lisp (file)

Method: (setf node-item) NEW-VALUE (NODE node)

automatically generated writer method

Source

fibonacci-heap.lisp (file)

Generic Function: node-last OBJECT
Generic Function: (setf node-last) NEW-VALUE OBJECT
Package

cl-heap

Methods
Method: node-last (NODE node)

automatically generated reader method

Source

fibonacci-heap.lisp (file)

Method: (setf node-last) NEW-VALUE (NODE node)

automatically generated writer method

Source

fibonacci-heap.lisp (file)

Generic Function: node-marked-p OBJECT
Generic Function: (setf node-marked-p) NEW-VALUE OBJECT
Package

cl-heap

Methods
Method: node-marked-p (NODE node)
Method: (setf node-marked-p) NEW-VALUE (NODE node)

Used to implement cascading cuts.

Source

fibonacci-heap.lisp (file)

Generic Function: node-next OBJECT
Generic Function: (setf node-next) NEW-VALUE OBJECT
Package

cl-heap

Methods
Method: node-next (NODE node)

automatically generated reader method

Source

fibonacci-heap.lisp (file)

Method: (setf node-next) NEW-VALUE (NODE node)

automatically generated writer method

Source

fibonacci-heap.lisp (file)

Generic Function: node-parent OBJECT
Generic Function: (setf node-parent) NEW-VALUE OBJECT
Package

cl-heap

Methods
Method: node-parent (NODE node)

automatically generated reader method

Source

fibonacci-heap.lisp (file)

Method: (setf node-parent) NEW-VALUE (NODE node)

automatically generated writer method

Source

fibonacci-heap.lisp (file)

Generic Function: node-rank OBJECT
Generic Function: (setf node-rank) NEW-VALUE OBJECT
Package

cl-heap

Methods
Method: node-rank (NODE node)
Method: (setf node-rank) NEW-VALUE (NODE node)

The number of children the node has.

Source

fibonacci-heap.lisp (file)

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 (file)

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

cl-heap

Source

binary-heap.lisp (file)

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

cl-heap

Source

fibonacci-heap.lisp (file)

Methods
Method: unmark-node (NODE node)

Previous: , Up: Internal definitions   [Contents][Index]

5.2.4 Classes

Class: node ()

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

Package

cl-heap

Source

fibonacci-heap.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: item
Initargs

:item

Readers

node-item (generic function)

Writers

(setf node-item) (generic function)

Slot: parent
Readers

node-parent (generic function)

Writers

(setf node-parent) (generic function)

Slot: child
Readers

node-child (generic function)

Writers

(setf node-child) (generic function)

Slot: rank

The number of children the node has.

Initform

0

Readers

node-rank (generic function)

Writers

(setf node-rank) (generic function)

Slot: marked

Used to implement cascading cuts.

Readers

node-marked-p (generic function)

Writers

(setf node-marked-p) (generic function)

Slot: next
Readers

node-next (generic function)

Writers

(setf node-next) (generic function)

Slot: last
Readers

node-last (generic function)

Writers

(setf node-last) (generic function)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   C   F   L  
Index Entry  Section

C
cl-heap.asd: The cl-heap<dot>asd file
cl-heap/binary-heap.lisp: The cl-heap/binary-heap<dot>lisp file
cl-heap/condition.lisp: The cl-heap/condition<dot>lisp file
cl-heap/fibonacci-heap.lisp: The cl-heap/fibonacci-heap<dot>lisp file
cl-heap/heap.lisp: The cl-heap/heap<dot>lisp file
cl-heap/package.lisp: The cl-heap/package<dot>lisp file
cl-heap/priority-queue.lisp: The cl-heap/priority-queue<dot>lisp file

F
File, Lisp, cl-heap.asd: The cl-heap<dot>asd file
File, Lisp, cl-heap/binary-heap.lisp: The cl-heap/binary-heap<dot>lisp file
File, Lisp, cl-heap/condition.lisp: The cl-heap/condition<dot>lisp file
File, Lisp, cl-heap/fibonacci-heap.lisp: The cl-heap/fibonacci-heap<dot>lisp file
File, Lisp, cl-heap/heap.lisp: The cl-heap/heap<dot>lisp file
File, Lisp, cl-heap/package.lisp: The cl-heap/package<dot>lisp file
File, Lisp, cl-heap/priority-queue.lisp: The cl-heap/priority-queue<dot>lisp file

L
Lisp File, cl-heap.asd: The cl-heap<dot>asd file
Lisp File, cl-heap/binary-heap.lisp: The cl-heap/binary-heap<dot>lisp file
Lisp File, cl-heap/condition.lisp: The cl-heap/condition<dot>lisp file
Lisp File, cl-heap/fibonacci-heap.lisp: The cl-heap/fibonacci-heap<dot>lisp file
Lisp File, cl-heap/heap.lisp: The cl-heap/heap<dot>lisp file
Lisp File, cl-heap/package.lisp: The cl-heap/package<dot>lisp file
Lisp File, cl-heap/priority-queue.lisp: The cl-heap/priority-queue<dot>lisp file

Jump to:   C   F   L  

Next: , Previous: , Up: Indexes   [Contents][Index]

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): Exported generic functions
(setf binary-heap-extension-factor): Exported generic functions
(setf node-child): Internal generic functions
(setf node-child): Internal generic functions
(setf node-item): Internal generic functions
(setf node-item): Internal generic functions
(setf node-last): Internal generic functions
(setf node-last): Internal generic functions
(setf node-marked-p): Internal generic functions
(setf node-marked-p): Internal generic functions
(setf node-next): Internal generic functions
(setf node-next): Internal generic functions
(setf node-parent): Internal generic functions
(setf node-parent): Internal generic functions
(setf node-rank): Internal generic functions
(setf node-rank): Internal generic functions

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

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

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

D
decrease-key: Exported generic functions
decrease-key: Exported generic functions
decrease-key: Exported generic functions
delete-from-heap: Exported generic functions
delete-from-heap: Exported generic functions
delete-from-heap: Exported generic functions
delete-node: Internal generic functions
delete-node: Internal generic functions
delete-node: Internal generic functions
dequeue: Exported generic functions
dequeue: Exported generic functions
do-each-node: Internal macros

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

F
Function, children-positions: Internal functions
Function, parent-position: Internal functions

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

H
heap-error-message: Internal generic functions
heap-error-message: Internal generic functions
heap-key: Exported generic functions
heap-key: Exported generic functions
heap-size: Exported generic functions
heap-size: Exported generic functions
heap-size: Exported generic functions
heap-sorting-function: Exported generic functions
heap-sorting-function: Exported generic functions

I
is-empty-heap-p: Exported generic functions
is-empty-heap-p: Exported generic functions
is-empty-heap-p: Exported generic functions
is-node-root-p: Internal generic functions
is-node-root-p: Internal generic functions

L
link: Internal generic functions
link: Internal generic functions

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

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

P
parent-position: Internal functions
peep-at-heap: Exported generic functions
peep-at-heap: Exported generic functions
peep-at-heap: Exported generic functions
peep-at-queue: Exported generic functions
peep-at-queue: Exported generic functions
percolate-down: Internal generic functions
percolate-down: Internal generic functions
percolate-up: Internal generic functions
percolate-up: Internal generic functions
pop-heap: Exported generic functions
pop-heap: Exported generic functions
pop-heap: Exported generic functions

Q
queue-size: Exported generic functions
queue-size: Exported generic functions

U
unmark-node: Internal generic functions
unmark-node: Internal generic functions

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

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   C   D   E   H   I   K   L   M   N   P   R   S  
Index Entry  Section

C
child: Internal classes
count: Exported classes

D
data: Exported classes

E
extension-factor: Exported classes

H
heap: Exported classes

I
item: Internal classes

K
key: Exported classes

L
last: Internal classes

M
marked: Internal classes
message: Exported conditions
message: Exported conditions

N
next: Internal classes

P
parent: Internal classes

R
rank: Internal classes
root: Exported classes

S
Slot, child: Internal classes
Slot, count: Exported classes
Slot, data: Exported classes
Slot, extension-factor: Exported classes
Slot, heap: Exported classes
Slot, item: Internal classes
Slot, key: Exported classes
Slot, last: Internal classes
Slot, marked: Internal classes
Slot, message: Exported conditions
Slot, message: Exported conditions
Slot, next: Internal classes
Slot, parent: Internal classes
Slot, rank: Internal classes
Slot, root: Exported classes
Slot, sort-fun: Exported classes
sort-fun: Exported classes

Jump to:   C   D   E   H   I   K   L   M   N   P   R   S  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

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

B
binary-heap: Exported classes

C
cl-heap: The cl-heap system
cl-heap: The cl-heap package
cl-heap-asdf: The cl-heap-asdf package
Class, binary-heap: Exported classes
Class, fibonacci-heap: Exported classes
Class, heap: Exported classes
Class, node: Internal classes
Class, priority-queue: Exported classes
Condition, heap-error: Exported conditions
Condition, key-error: Exported conditions

F
fibonacci-heap: Exported classes

H
heap: Exported classes
heap-error: Exported conditions

K
key-error: Exported conditions

N
node: Internal classes

P
Package, cl-heap: The cl-heap package
Package, cl-heap-asdf: The cl-heap-asdf package
priority-queue: Exported classes

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

Jump to:   B   C   F   H   K   N   P   S