[Haskell-cafe] Performance of functional priority queues

Sebastian Sylvan sebastian.sylvan at gmail.com
Mon Jun 15 05:40:32 EDT 2009

On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:

> There's a current thread in the Erlang mailing list about
> priority queues.  I'm aware of, for example, the Brodal/Okasaki
> paper and the David King paper. I'm also aware of James Cook's
> priority queue package in Hackage, have my own copy of Okasaki's
> book, and have just spent an hour searching the web.
> One of the correspondents in that thread claims that it is
> provably impossible to have an efficient priority queue implementation

A priority queue based on skewed binomial heaps is asymptotically optimal
(O(1) for everything except deleteMin which is O(log n)), so if that's what
he means by "efficient" then he's most definitely wrong. If he's talking
about "small constant factors" then it's harder to understand what he's
referring to more precisely, and therefore what he means by "provably".

Sebastian Sylvan
UIN: 44640862
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090615/e39453c5/attachment.html

More information about the Haskell-Cafe mailing list