[Haskell-cafe] Priority queue

[Sebastian Sylvan]

On 12/15/05, Joel Reymont <joelr1 at gmail.com> wrote:
> 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