<br><br>
<div class="gmail_quote">On Mon, Jun 15, 2009 at 4:18 AM, Richard O&#39;Keefe <span dir="ltr">&lt;<a href="mailto:ok@cs.otago.ac.nz">ok@cs.otago.ac.nz</a>&gt;</span> wrote:<br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">There&#39;s a current thread in the Erlang mailing list about<br>priority queues.  I&#39;m aware of, for example, the Brodal/Okasaki<br>
paper and the David King paper. I&#39;m also aware of James Cook&#39;s<br>priority queue package in Hackage, have my own copy of Okasaki&#39;s<br>book, and have just spent an hour searching the web.<br><br>One of the correspondents in that thread claims that it is<br>
provably impossible to have an efficient priority queue implementation</blockquote>
<div> </div>
<div>A priority queue based on skewed binomial heaps is asymptotically optimal (O(1) for everything except deleteMin which is O(log n)), so if that&#39;s what he means by &quot;efficient&quot; then he&#39;s most definitely wrong. If he&#39;s talking about &quot;small constant factors&quot; then it&#39;s harder to understand what he&#39;s referring to more precisely, and therefore what he means by &quot;provably&quot;.</div>

<div> </div></div>-- <br>Sebastian Sylvan<br>+44(0)7857-300802<br>UIN: 44640862<br>