A binary heap based priority queue implementation with efficient support for find, update, replace, and delete operations.

pettomato-indexed-priority-queue

This is a binary heap based priority queue implementation. In addition
to the properties and operations common to all binary heaps (see
http://en.wikipedia.org/wiki/Binary_heap), this implementation also
supports efficient find, update, replace, and delete operations.

Please see the docstrings of the exported symbols for more
information, especially make-empty-queue for an explanation of how
item lookups are achieved.

--------------------------------
Acknowledgments

This code was originally based off of Peter Norvig's implementation
found here:

http://aima.cs.berkeley.edu/lisp/utilities/queue.lisp

Norvig's code was built on top of the heap algorthms in "Introduction
to Algorithms" by Corman, Leiserson, and Rivest. I trivially updated
some of that code to match the 2nd edition of the book by Corman,
Leiserson, Rivest, and Stein. Specifically, I updated the referenced
page numbers in the docstrings and implemented the Heap-Increase-Key
algorithm (called improve-key in my code), which was not in the first
edition (and is very useful for the new operations I added).


fiveam

Test suite for pettomato-indexed-priority-queue.

pettomato-indexed-priority-queue

Upstream URL

Author

License

pettomato-indexed-priority-queue

Version:

License:

Authors:

Dependencies:

pettomato-indexed-priority-queue-tests

Version:

License:

Authors:

Dependencies:

Dependencies (1)

Dependents (1)