A heap of possibilities

I needed a priority queue a few months ago, and didn't have a predefined one, so I used a sorted list, since n was always small. But that won't work for many applications. Yesterday I wanted a pq for a best-first search with a potentially large n. Obviously a heap was the answer. But the modest trouble of implementing one was enough to discourage me from trying that search. It wasn't in the standard library, so it was too much trouble to bother with.

Heaps are quite useful, and quite stereotyped, so they make good candidates for a standard library. I think they (like most data structures) would be most convenient as a heap type which supports the same operations as other collections, but with the particular performance characteristics of heaps. In addition, it's probably a good idea to expose the two internal reheap operations (adding and removing) so they can be reused for variations like limited-size heaps, or heapifying an existing array as in heapsort or heap-select.

And they should be ordinary destructive heaps, not functional ones. The motivation for heaps is performance, and heaps that require consing can't compete with those built on arrays. The flexibility functional heaps offer isn't worth the performance cost, because heaps are almost always used linearly.

When you have heaps, some fancy algorithms become much easier. The search I wanted yesterday, for example (in pseudo-Lisp):

(defun a* (expand min-cost done? init)
  "Best-first heuristic graph search. Starting from INIT,
find the lowest-cost node that satisfies DONE?, where
NEIGHBORS is a function on a node that returns a list of
its neighbors, and MIN-COST is function from a node to a
lower bound on the cost of any node reachable from it."
  (def pq (heap (o* < min-cost)))
  (def (step x)
    (if (done? x)
      (do (each (expand x) (add! _ pq))
          (aif (pop! pq)
            (step it)
  (step init))

If you really want to make fancy algorithms easy, you could include functions like that one in the standard library. The greatest strength of functional programming (in the high-order sense) is the ability to abstract algorithms; we might as well use it.


  1. SBCL has a heap and priority queue in its timer implementation. I originally wrote it for myself, and gabor melis fixed a few glitches to include in sbcl. It's public domain and can be ripped out and reused as you like. The file, I think, is timer.lisp.

  2. Oh, thanks! I would have been using SBCL, too, had I actually written that search. But on reflection I decided the problem didn't map into a graph very well - the search path would have been way too wide - so I went back to trying to optimize a problem-specific search.

    The only difference between timer.lisp's heap implementation and real, useful library is whether it's mentioned in the documentation. :) Although that wouldn't have helped me, since I've barely looked at SBCL's docs, and consequently I have only the faintest idea what non-CL libraries it has.


It's OK to comment on old posts.