[Haskell-cafe] Performance of functional priority queues
sebastian.sylvan at gmail.com
Mon Jun 15 09:43:00 EDT 2009
Is that not what I said?
On Mon, Jun 15, 2009 at 2:12 PM, Lennart Augustsson
<lennart at augustsson.net>wrote:
> A priority queue can't have all operations being O(1), because then
> you would be able to sort in O(n) time. So O(log n) deleteMin and
> O(1) for the rest is as good as it gets.
> On Mon, Jun 15, 2009 at 10:40 AM, Sebastian
> Sylvan<sebastian.sylvan at gmail.com> wrote:
> > On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe <ok at cs.otago.ac.nz>
> >> 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
> > 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
> > +44(0)7857-300802
> > UIN: 44640862
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe