[Haskell-cafe] Priority queue
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).
More information about the Haskell-Cafe