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