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.
CL-HEAP is licensed under the GPL. Its web page can be found at http://common-lisp.net/project/cl-heap/.
You can install this using quicklisp.