Feedback request: priority queues in containers

Louis Wasserman wasserman.louis at gmail.com
Tue Mar 16 14:58:05 EDT 2010


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/glasgow-haskell-users/attachments/20100316/6af27697/attachment.html


More information about the Glasgow-haskell-users mailing list