[Haskell-cafe] Performance of functional priority queues

Jon Harrop jon at ffconsultancy.com
Fri Dec 25 18:27:26 EST 2009

On Friday 25 December 2009 19:59:39 Louis Wasserman wrote:
> >> One of the correspondents in that thread claims that it is
> >> provably impossible to have an efficient priority queue implementation
> >> without mutability.  I think he's cuckoo.  But I'd like to have some
> >> numbers to back me up.
> He is cuckoo, and here's proof:
> http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf
> <http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf>This demonstrates a
> functional priority queue that performs every desired operation in
> asymptotically optimal time...

You're assuming he meant asymptotic time complexity.

Dr Jon Harrop, Flying Frog Consultancy Ltd.

More information about the Haskell-Cafe mailing list