[Haskell-cafe] Performance of functional priority queues

[Lennart Augustsson]

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.sylvan at gmail.com> wrote:
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>