Is that not what I said? On Mon, Jun 15, 2009 at 2:12 PM, Lennart Augustsson <lenn...@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.syl...@gmail.com> wrote: > > > > > > On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe <o...@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@haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
