A brief update:<br><br>I&#39;m continuing to work on a priority queue implementation for containers.  I&#39;ve pretty much settled on a variation on a binomial heap that actually has the type-checker guarantee the correct binomial structure.  It has the following properties:<br>

<ul><li>Amortized O(1) insertion.  There are variations (skew binomial heaps) with guaranteed O(1) insertion, but they add tremendously to the complexity of the implementation, if they work at all with this approach (I&#39;ve encountered some difficulties with this approach).  I think this is fine, as-is.</li>

<li>Worst-case O(log n) union.  (If you&#39;re working in a single-threaded fashion, I am pretty convinced that you can treat union as amortized O(0), but O(log n) is pretty good in any event.)</li><li>O(1) find-min.<br>
</li>
<li>Worst-case O(log n) extract.</li></ul>The primary competing implementation is a pairing heap implementation, with the following properties:<br><ul><li>O(1) insertion, union, and find-min, worst-case and amortized.</li>

<li>Amortized O(log n) extract, but worst-case O(n).  If used in a persistent context, it&#39;s possible that a user could encounter a situation that performs linear-time extraction operations many times.  (This is my primary concern with this implementation, especially given that containers users will be expecting a reliable data structure that won&#39;t break down.)</li>

</ul>For a simple heap sort, the pairing heap is just about twice as fast as the binomial heap, but I think having reasonable worst-case guarantees for containers users is important enough to dominate that concern.<br><br>

There has also been some discussion of using priority search queues --
priority queues in which you can also find previously inserted elements
-- but I think this is more appropriate for a separate package, and not
something that is necessarily needed by most users.<br><br>I&#39;ve also written a wide variety of utility functions, which you can see in the implementation <a href="http://hackage.haskell.org/trac/ghc/attachment/ticket/3909/containers-pqueue.4.patch">here</a>.  In particular, a number of Data.List functions are modified to apply to priority queues, including take, drop, splitAt, takeWhile, dropWhile, span, break, filter, and partition.  All of these are implemented asymptotically optimally.<br>

<br>Do people have any other thoughts?<br><br clear="all">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>