Priority Queues, or lack thereof

[Sebastian Sylvan]

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