I have something I call a "HashHeap" which I use in my "RevModeDiff" (automatic differentiation) module. Both are here: http://ofb.net/~frederik/futility/ I wrote it when I was first learning Haskell so it's a bit unpolished, but I think some reincarnation of the same concept might be a good complement to a priority queue implementation such as yours. What it is is a map of priorities to hashtables of keys to values. Each value has a priority and a key. This allows you to insert something with a non-unique priority and then remove it later. You can also remove everything with the smallest priority - all the values in the smallest-priority hash table. It does take log(n) time to find the top priority. In my application this is not a problem, though, since many things share the same priority. If I were to have taken the purely functional route of using a map of (priority,value) tuple keys then it might be a bigger problem. However, my values are not Ord so that route was not allowed. I often find that when I want to use priority queues, I'm annoyed by the fact that I can't remove something which is not the minimum. Suppose I'm scheduling jobs and I want to cancel a job, etc. 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. One more thing, about the order of arguments: insertBy :: (a -> a -> Ordering) -- ^ An ordering function -> a -- ^ The element to insert -> PriorityQueue a -- ^ The priority queue in which the element will be inserted -> PriorityQueue a -- ^ The resulting priority queue I see the same kind of argument ordering in Data.Map. Why is the data structure last? Usually one would think that the arguments should be ordered from "most constant" to "least constant" so that currying is as useful as possible. But surely the data structure is "more constant" than its elements, even (especially?) if it is persistent. Cheers, Frederik On Thu, Aug 11, 2005 at 08:16:56PM +0200, Sebastian Sylvan wrote:
I've been puzzled by the lack of a priority queue implementation in the hierarchical libraries for some time. Sure, you could use a Data.Map as a priority queue, but something about having to pay O(log n) to find the smallest element bugs me.
So, I decided to implement my own priority queue with optimal asymptotic time complexity. That is: insert : O(1) findMin : O(1) meld : O(1) deleteMin : O(log n)
It's based heavily on the strategy detailed in the paper "Optimal Purely Functional Priority Queues" by Gerth StØlting Brodal and Chris Okasaki.
This is asymptotically better than other, simpler, data structures, but the "constant factor" is likely very high (I haven't done any sort of serious benchmarking). I figured that if you have a small data set, the speed isn't going to matter much anyway, and if you have a large enough data set the asymptotically better data structure is faster.
Anyway This was just something I threw together when I had some spare time. There may be misstakes in there, there's probably tons of room for improvement, but at least it's a priority queue!
Download at: http://www.dtek.chalmers.se/~sylvan/PriorityQueue/
----------------------------------------------------------------------------------------------------------- File Description ----------------------------------------------------------------------------------------------------------- PrimPQ.hs The internal workings of the skewed binomial tree PriorityQueue.hs The main priority queue module PriorityQueueTests.hs Some quickcheck properties -----------------------------------------------------------------------------------------------------------
/S
-- Sebastian Sylvan +46(0)736-818655 UIN: 44640862 _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries