[Haskell-cafe] Performance of functional priority queues

[Sebastian Sylvan]

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>
> 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
> > +44(0)7857-300802
> > UIN: 44640862
> >
>  > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> >
>



-- 
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090615/4e61d3e2/attachment.html