[Haskell-cafe] Performance of functional priority queues

[Jon Harrop]

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.
http://www.ffconsultancy.com/?e