[Haskell-cafe] Performance of functional priority queues
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>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