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)
      x
      (do (each (expand x) (add! _ pq))
          (aif (pop! pq)
            (step it)
            nil))))
  (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.