Priority Queues, or lack thereof

Sebastian Sylvan sebastian.sylvan at
Thu Aug 11 14:16:56 EDT 2005

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

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:

File                               Description
PrimPQ.hs                    The internal workings of the skewed binomial tree
PriorityQueue.hs            The main priority queue module
PriorityQueueTests.hs    Some quickcheck properties


Sebastian Sylvan
UIN: 44640862

More information about the Libraries mailing list