Re: [Haskell-cafe] Performance of functional priority queues

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 wrote:

Is that not what I said?

On Mon, Jun 15, 2009 at 2:12 PM, Lennart Augustsson 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 wrote:

...

On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe 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