<span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; ">>> One of the correspondents in that thread claims that it is<br>>> provably impossible to have an efficient priority queue implementation<br>
>> without mutability. I think he's cuckoo. But I'd like to have some<br>>> numbers to back me up.</span><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br>
</span></font></div><div><span class="Apple-style-span" style="font-size: 13px; "></span><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">He is cuckoo, and here's proof: <a href="http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf">http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf</a></span></font></div>
<div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br></span></font></div><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><a href="http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf"></a>This demonstrates a functional priority queue that performs every desired operation in asymptotically optimal time. Granting that its constant factor could be significantly improved, realize that there are more complicated functional data structures with similar asymptotic guarantees. (Observation: I'm pretty sure that the Fibonacci heap is actually surprisingly functional.)<br>
</span></font><div><span class="Apple-style-span" style="font-size: 13px; "></span><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br clear="all">
</span></font>Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br><a href="http://profiles.google.com/wasserman.louis">http://profiles.google.com/wasserman.louis</a><br>
<br><br></div></div>