On 12/15/05, Joel Reymont
Does anyone have priority queue Haskell code that they would be willing to share or point me to?
Thanks, Joel
Here's one I wrote some time ago: http://www.dtek.chalmers.se/~sylvan/PriorityQueue/ It's implemented as skewed binomial trees. The oeprations insert, findMin and meld are all O(1), deleteMin is O(log n). That's optimal (well, the theoretical optimum is that all operations are O(1) except one which is O(log n), it could theoretically be some other function that's O(log n), but for this implementation it's deleteMin). In practice, for fewer elements, it may be faster to use other structures though (like lazy pairing heaps). The constant term is kinda high (though not *that* bad). /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862