Copyright © 2002, 2003, 2004 Gene Michael Stover. All rights reserved. Permission to copy, store, & view this document unmodified & in its entirety is granted.
This is a straightforward implementation of a data structure called a heap. It's mostly a Lisp version of the heap implementation Mark Allen Weiss gives in [Wei97]. Doctor Weiss's implementation is for C, not Lisp, so my mostly direct translation probably is not as Lispy as it could be. Then again, I don't see much that's particularly Lispy about heaps in the first place. (See Appendix A for some more details about this thought.)
The source code for this heap library is licensed according to the terms of the Gnu Public License (GPL). The GPL is available in HTML format at http://www.gnu.org/licenses/gpl.html & in text format at http://www.gnu.org/licenses/gpl.txt. Further information about the GPL & other software license agreements is available at http://www.gnu.org/licenses/licenses.html.
This documentation is not licensed according to the GPL. It is copyrighted by Gene Michael Stover. The official copyright notice is at the beginning of the document.
The source code for the heap module is in heap.lisp.
Because a heap is an implementation, not a generic container with a polymorphic interface. It's beneficial to have a priority queue with the same interface as a queue's & a stack's, but a heap is just a heap. When you need polymorphism, you can use a heap to implement a priority queue, but when you know you need a heap, you might as well use a heap.
I intend to copy this heap module into CyberTiggyr's Tigris library of utilities for Lisp, but I left the implementation here in the raw, not in a package, to keep the code clean. I wanted the code to be simple so I could test it & discuss it here.
Test programs are in test.lisp. You can run all the tests by evaluating the expression ``(check *tests*)'', or you can have my web server run them. The source code for that CGI program is test0000.sh.
The test.lisp file also contains some functions to estimate the performance of this heap library.
function
demo-numbers &optional (count 10000)
Makes a heap, fills it with count random numbers, then removes all of them. Prints count, the number of seconds required for the operations, & the rate. Returns the rate.
function
demo-game
Simulate a game with an event loop to see how quickly a game could process events (if processing an event required no time & the only work was in the event loop itself). Return the number of messages per second.
Approximates a game's event queue by putting 10,000 events in the queue, then inserts & removes elements one at a time for a while. Elements are random integers.
My laptop, Plague, a 750 MHz Pentium 3, running clisp 2.28 in interpreted mode, does 1493 insert/remove operations per second. With clisp in auto-compilation mode (``clisp -C''), it does 11,111 operations per second.
If a game's frame rate is 30 per second, 11,111 operatins per second translates to about 370 events per frame. So 370 is an upper bound on the number of operations per frame a game should demand.
Figure 1 shows how to create a queue of integers, put some integers in it, & then remove them. This example doesn't check for empty queues. The source code is in ex00.lisp.
You can ask the heap if it's empty with heap-empty-p. Figure 2 is like the previous example except that it prints everything in the heap instead of assuming the heap contains just three items.
The source code for this example is in ex00.lisp.
With a heap, a heap sort is easy to write.
Figure 3 shows a heap sort function. It's not as general as Lisp's built-in sorting function; this example heap sort assumes the sequence to sort is a list. It always returns a list of new cons cells, which isn't optimal, but it still demonstrates a heap sort using a heap.
A little (or a lot) of thought about heaps & about the sort function in Figure 3 might cause one to notice that all the items are inserted before any items are removed. One might further wonder ``Is there a way to optimize bulk insertions?'' The answer is ``Yes, with the :initial-contents keyword argument of create-heap. The heap sort function in Figure 4 takes advantage of that.
The second heap sort function, heap-sort-smart, doesn't do any insertions explicitly. Instead, it lets create-heap insert the items when the heap is initialized. In theory that is faster than a bunch of separate inserts.
Is it really faster? The function in Figure 5 compares the two heap sorts & prints the number of seconds required for each sort. How much faster is heap-sort-smart? Only about 8.5 percent, which is probably easily explained by the lack overhead from calling heap-insert in a loop. So much for theory. I'd say the main benefit heap-sort-smart has over heap-sort-basic is that it's shorter.
The source code for both heap sort functions & for ex11 is in ex11.lisp.
The complete source file is heap.lisp.
function
create-heap less-fn &key (order 2) (initial-contents nil)
Creates a new heap with make-heap, initializes it with heap-init, & returns it.
Items in the heap are ordered according to less-fn. In other words, if two elements a & b are in the heap, a will be before b if (funcall less-fn a b) returns truth.
Initial-contents must be a list, though nil is acceptable. If initial-contents is a non-empty list, the heap's contents are intiailized to the values in that list.
order is the number of children each node in the heap has. It defaults to 2, which is a binary heap. It could be, say, 3 or 4 or 10. It must be an integer greater than 1.
function
heap-clear heap
Removes all elements from the heap. Does not return them. Faster than calling heap-remove in a loop until the heap is empty.
function
heap-count heap
Returns the number of items in the heap. That is the number of times heap-insert has been called, less the number of times heap-remove has been called. The count of an empty heap is zero, but if you just need to test whether a heap is empty, it might be a good idea to use heap-empty-p instead.
function
heap-empty-p heap
Returns true if & only if the heap is empty.
I recommend using heap-empty-p to test for an empty heap because it is probably more readable than fetching the count & comparing it to zero, & because heap-empty-p might be slightly more efficient than using heap-count for the task.
function
heap-insert heap x
Insert item x into the heap. Return x, which probably isn't very useful.
function
heap-peek heap
If the heap is not empty, return the minimum (first) item in the heap. Do not remove that item from the heap.
It is an error if the heap is empty.
function
heap-remove heap (fn #'(lambda (h x) t))
Remove the first element in the heap that satisfies the predicate fn. Returns the element that was removed, or nil if no element matched the predicate.
The default value for fn is a predicate which matches the first item in the heap. So ``(heap-remove h)'' removes & returns the first element in the heap, or nil if the heap was already empty.
structure
heap
Normally, you don't need to think about the innards of the heap structure.
Here are the members of the heap structure:
Because heap is a structure, each of the members has an accessor defined by defstruct in the usual way. The heap-less-fn & heap-max-count accessors, used for read-only, might be useful fairly often. The heap-a accessor should be used only if terribly necessary.
Using (setf heap-max-count) might be useful if you want to reset the max-count to zero because, say, you want to measure the heap capacity required by sections of a program.
function
heap-init heap less-fn &key (order 2) (initial-contents nil)
Initialize the indicated heap. If initial-contents is a non-empty list, the heap's contents are intiailized to the values in that list; they are ordered according to less-fn. initial-contents must be a list or nil.
function
make-heap &optional ...
Returns a new heap structure. Before you use it, you should initialize it with heap-init.
Avoid using the symbols here. They might be necessary for testing or validity checks, but avoid using them in production code.
function
heap-find-idx heap fnp
Return the index of the element in heap which satisfies the predicate fnp. If there is no such element, return the fill pointer of heap's array A.
fnp is a function of two arguments, the heap & an element in the heap.
function
lesser-child heap parent
Parent is the index of an element in (heap-a heap).
Return the index of the lesser child of parent. If there's one child, returns the index of that child. If there are no children, return (fill-pointer (heap-a heap)).
function
percolate-down heap hole x
Move the ``hole'' (unused element) of the heap to larger indexes until its position is appropriate to hold x. Return the new index of the hole.
Heap is a heap as returned by create-heap.
Hole is the index of an element in the heap's array
((heap-a heap)). Assume
,
where len is (length (heap-a heap)).
X is an object that (heap-less-fn heap) can compare to other objects in the heap.
function
percolate-up heap hole x
Private. Moves the hole until it's in a location suitable for holding x. Does not actually bind x to the hole. Returns the new index of the hole. The hole itself percolates down; it's the x that percolates up.
In early 2004, I came across Purely Functional Data Structures, by Chris Okasaki. In several places in that book, Mister Okasaki describes heap implementations which are more functional than the one I have used here. (Remember that I simply transcribed a heap implementation from a plain old imperative data structures book.)
I suspect that one of the heap implementations Mr. Okasaki describes would have a more elegant, Lispy feel than the one I've described in this article, & I'm curious to see how performance would compare. I haven't had time to try any of the more functional heap implementations, though.
By the way, I fervently recommend that book, Purely Functional Data Structures, to any Lisp programmer. It had been many years since I had read such an eye-opening programming book as that. (I guess the book which gave me my previous eye-opening programming experience was Peter Norvig's Paradigms of Artificial Intelligence: Case Studies in Common Lisp.)
Other formats of this document are available for your printing & reading enjoyment.
There is a PostScript version.
There is a Device Independent (DVI) version which was the direct output of the LATEX compiler.
