
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