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 algorithms.

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

(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 here. The preferred installation method is to use quicklisp:

(quicklisp:quickload 'cl-heap)

(quicklisp:quickload 'cl-heap-tests)

(quicklisp:quickload 'cl-heap-tests)

The README file covers the library's API, and gives examples on how to use it.

Rudy Neeser

You can access the code repository at github.

CL-HEAP is provided under the GPL, version 3.