Priority Queues, or lack thereof

[Frederik Eaton]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>