25 Dec
2009
25 Dec
'09
11:27 p.m.
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.pdfThis 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