<blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
I'm not sure about some of that. Imperative queues sometimes offer</blockquote><meta http-equiv="content-type" content="text/html; charset=utf-8"><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; "><blockquote>
O(1) decreaseKey and O(lg n) delete by storing pointers to elements in</blockquote><blockquote>a priority queue. The usual purely functional PQs can only offer O(n)</blockquote><blockquote>decreaseKey and O(n) delete. Purely functional PSQs can offer O(lg n)</blockquote>
<blockquote>decreaseKey and O(lg n) delete.</blockquote><blockquote><br></blockquote><blockquote>Minimum spanning tree is a common application for PQs that makes good</blockquote><blockquote>use of decreaseKey.<br></blockquote>
That example did occur to me, but I feel okay about following the examples of Java and C++ STL, which offer priority queue implementations, but those implementations don't support decreaseKey. </span><div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; "><br>
</span></div><div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; ">You might be able to convince me that we should offer PSQueues in addition to PQueues, but I don't think they should be merged, for the following reason. Using the PSQueue package, which is essentially a copy of Ralf Hinze's original implementation, yields the following benchmark for heapsorting 25000 Ints:</span></div>
<div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; "><div><br></div><div>Binomial: 0.000 3.240 2.180 4.000 8.001</div><div>PSQ: 8.001 13.241 2.882 12.001 24.002</div>
<div><br></div><div>I'm really not okay with that kind of performance loss for added functionality that not everyone needs.</div></span></div><div><div><br><div>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 class="gmail_quote">On Tue, Mar 16, 2010 at 1:58 PM, Louis Wasserman <span dir="ltr"><<a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im"><span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse"><blockquote><br>Why not use Okasaki & Brodal's "Optimal Purely Functional Priority</blockquote>
<blockquote>Queues"? They offer worst case:</blockquote><blockquote><br></blockquote><blockquote>* O(1) union, findMin, and insert</blockquote><blockquote>* O(lg n) deleteMin</blockquote>The primary reason that we don't use this implementation is, quoting from the paper you yourself linked to,</span></div>
<div><div class="im">
<blockquote class="gmail_quote" style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 204);border-left-style:solid;padding-left:1ex">
Our data structure is reasonably efficient in practice;<br>however, there are several competing data structures that, although<br>not asymptotically optimal, are somewhat faster than ours in practice.</blockquote><blockquote class="gmail_quote" style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 204);border-left-style:solid;padding-left:1ex">
<div>Hence, our work is primarily of theoretical interest.</div></blockquote><div><br></div><div>The current implementation is considerably faster than Okasaki's implementation in practice, based on our benchmarks. Furthermore, the asymptotics are really pretty good, and the constant factors appear to be relatively low.</div>
<div><br></div><div>I wrote a pretty efficient skew binomial heap implementation -- the first step of Okasaki's approach -- and found it was already slower than the optimized binomial heap. I'm not sure whether or not I uploaded that benchmark, though. I'll do that at some point today, just to keep everyone happy.</div>
</div><div><span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse"><br></span><div class="im">Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com" target="_blank">wasserman.louis@gmail.com</a><br>
<a href="http://profiles.google.com/wasserman.louis" target="_blank">http://profiles.google.com/wasserman.louis</a><br>
</div></div></div>
</blockquote></div><br></div></div></div>