Introduction
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
News
-
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.
Mailing Lists
Download
Version 0.1.3 of CL-HEAP is available
here.
It can also be installed using ASDF-INSTALL.
Documentation
The README file covers
the library's API, and gives examples on how to use it.
Project members
Rudy Neeser
Sources
You can
browse our SVN repository or download the current development tree via
anonymous access, as described here
License
CL-HEAP is provided under the GPL, version 3.