CL-HEAP

Heap and priority queue data structures

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

Download

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)

Documentation

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

Project members

Rudy Neeser

Sources

You can access the code repository at github.

License

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