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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
