Feedback request: priority queues in containers

[Louis Wasserman]

Why not use Okasaki & Brodal's "Optimal Purely Functional Priority

Queues"? They offer worst case:


* O(1) union, findMin, and insert

* O(lg n) deleteMin

The primary reason that we don't use this implementation is, quoting from
the paper you yourself linked to,

> Our data structure is reasonably efficient in practice;
> however, there are several competing data structures that, although
> not asymptotically optimal, are somewhat faster than ours in practice.

Hence, our work is primarily of theoretical interest.
>

The current implementation is considerably faster than Okasaki's
implementation in practice, based on our benchmarks.  Furthermore, the
asymptotics are really pretty good, and the constant factors appear to be
relatively low.

I wrote a pretty efficient skew binomial heap implementation -- the first
step of Okasaki's approach -- and found it was already slower than the
optimized binomial heap.  I'm not sure whether or not I uploaded that
benchmark, though.  I'll do that at some point today, just to keep everyone
happy.

Louis Wasserman
wasserman.louis at gmail.com
http://profiles.google.com/wasserman.louis
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100316/6af27697/attachment-0001.html