<span class="Apple-style-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>
<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><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; "><br></span>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>
</div></div>