Heap and priority queue data structures


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



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)


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

Project members

Rudy Neeser


You can access the code repository at github.


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