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

Upstream URL


Austin Haas <>


This is a binary heap based priority queue implementation. In addition to the properties and operations common to all binary heaps (see, 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: 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).

Dependencies (1)

  • fiveam
  • GitHub
  • Quicklisp