CL-HEAP provides various implementations of heap data structures (a
binary heap and a Fibonacci heap) as well as an efficient priority
queue. The Fibonacci heap has interesting run time constraints,
with many operations occurring in constant or amortised constant
time, making it ideal for use in implementing other algorithms,
such as Dijkstra's shortest path and Prim's minimum spanning tree
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
- 9 June 2012. Moved repository to github: https://github.com/TheRiver/CL-HEAP.
- 4 April 2012. Version 0.1.5 released. Patches submitted by Michał Psota to reduce warnings produced by some compilers were applied. See the ChangeLog for details.
- 4 September 1010. Version 0.1.4 released. FIXNUM is no longer used as a specialising class in generic functions. They have been replaced with INTEGER instead. This should increase CL-HEAP's portability.
17 March 2010. Version 0.1.3 released. The tests have been separated into their own system, defined in cl-heap-tests.asd. They can be loaded using (asdf:oos 'asdf:load-op 'cl-heap-tests).
20 December 2009. Version 0.1.2 released, fixing a bug in the Binary Heap class that prevented the class from operating properly in SBCL 1.0.29.
19 June 2009. Version 0.1.1 released, fixing a bug in the Fibonacci Heap class.
24 March 2009. Version 0.1 released.
Version 0.1.5 of CL-HEAP is available
The preferred installation method is to use quicklisp:
file covers the library's API, and gives examples on how to use it.
You can access the code repository at github.
CL-HEAP is provided under the GPL, version 3.