Priority Queues, or lack thereof
joelkoerwer at gmail.com
Tue Aug 16 10:28:15 EDT 2005
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
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.
More information about the Libraries