Priority Queues, or lack thereof

[Joel Koerwer]

Sebastian Sylvan wrote:
> I can imagine that with an imperative data structure I could have it both
> ways - deletion of internal elements, and O(1) findMin. Is this not
> possible with a functional implementation? It doesn't seem to be a
> feature of your implementation. If it were possible, it seems like it
> might be nice to have it as part of the interface.

When implementing a physical simulation (many-body 1d gravity) I
needed a priority queue to schedule interactions that could handle
many updates. Each interaction produces 2 or 3 scheduling updates. My
first project in Haskell was a direct port of the imperative prototype
of this simulation. Mutable arrays (in the ST monad) held a binary
priority heap and a second array indexing each event in the heap.
Obviously a more elegant solution was desirable.

Then I ran across references to the Priority Search Queue. See Ralph
Hinze's "A Simple Implementation Technique for Priority Search
Queues".  http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-2001/2001-09.pdf

You get 0(1) findMin and O(log n) deleteMin, delete, and update.

This is just what I was looking for and much more flexible as the
foundation of a discreet event-based simulation library, the core of
which I intend to implement when I find the time...

But now, thanks to this thread, I'll first have to find time to check
out Lazy Pairing Heaps and the Edison Library in general.

Joel