[Haskell-cafe] Priority queue

Sebastian Sylvan sebastian.sylvan at gmail.com
Thu Dec 15 08:11:41 EST 2005

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:


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).


Sebastian Sylvan
UIN: 44640862

More information about the Haskell-Cafe mailing list