I wasn't contradicting you, just clarifying that this is indeed the optimal asymtotic complexity.
On Mon, Jun 15, 2009 at 3:43 PM, Sebastian Sylvan<sebastian.syl...@gmail.com> wrote: > 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 > > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
