Is that not what I said?<br><br>
<div class="gmail_quote">On Mon, Jun 15, 2009 at 2:12 PM, Lennart Augustsson <span dir="ltr">&lt;<a href="mailto:lennart@augustsson.net">lennart@augustsson.net</a>&gt;</span> wrote:<br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">A priority queue can&#39;t have all operations being O(1), because then<br>you would be able to sort in O(n) time.  So O(log n) deleteMin and<br>
O(1) for the rest is as good as it gets.<br>
<div>
<div></div>
<div class="h5"><br>On Mon, Jun 15, 2009 at 10:40 AM, Sebastian<br>Sylvan&lt;<a href="mailto:sebastian.sylvan@gmail.com">sebastian.sylvan@gmail.com</a>&gt; wrote:<br>&gt;<br>&gt;<br>&gt; On Mon, Jun 15, 2009 at 4:18 AM, Richard O&#39;Keefe &lt;<a href="mailto:ok@cs.otago.ac.nz">ok@cs.otago.ac.nz</a>&gt; wrote:<br>
&gt;&gt;<br>&gt;&gt; There&#39;s a current thread in the Erlang mailing list about<br>&gt;&gt; priority queues.  I&#39;m aware of, for example, the Brodal/Okasaki<br>&gt;&gt; paper and the David King paper. I&#39;m also aware of James Cook&#39;s<br>
&gt;&gt; priority queue package in Hackage, have my own copy of Okasaki&#39;s<br>&gt;&gt; book, and have just spent an hour searching the web.<br>&gt;&gt;<br>&gt;&gt; One of the correspondents in that thread claims that it is<br>
&gt;&gt; provably impossible to have an efficient priority queue implementation<br>&gt;<br>&gt;<br>&gt; A priority queue based on skewed binomial heaps is asymptotically optimal<br>&gt; (O(1) for everything except deleteMin which is O(log n)), so if that&#39;s what<br>
&gt; he means by &quot;efficient&quot; then he&#39;s most definitely wrong. If he&#39;s talking<br>&gt; about &quot;small constant factors&quot; then it&#39;s harder to understand what he&#39;s<br>&gt; referring to more precisely, and therefore what he means by &quot;provably&quot;.<br>
&gt;<br>&gt; --<br>&gt; Sebastian Sylvan<br>&gt; +44(0)7857-300802<br>&gt; UIN: 44640862<br>&gt;<br></div></div>
<div>
<div></div>
<div class="h5">&gt; _______________________________________________<br>&gt; Haskell-Cafe mailing list<br>&gt; <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>&gt; <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
&gt;<br>&gt;<br></div></div></blockquote></div><br><br clear="all">
<div></div><br>-- <br>Sebastian Sylvan<br>+44(0)7857-300802<br>UIN: 44640862<br>