DETAILS:

The proposed implementation benchmarked competitively with every alternative implementation that we tested, and offers good asymptotics in nearly every operation. Specifically, we use a binomial heap, which offers

O(log n) worst-case union
O(log n) worst-case extract (this in particular was a key objective of ours)
amortized O(1), worst-case O(log n) insertion. (In a persistent context, the amortized performance bound does not necessarily hold.)

This implementation seems to offer the best balance between practical performance and asymptotic behavior. Moreover, this implementation is extremely memory-efficient, resulting in better performance on large data sets. (See the ticket for benchmarks. The most accurate benchmarks are towards the end.)

A couple potentially contentious design decisions:

There is no distinction between keys and priority values. A utility type Prio p a with the instance Ord p => Ord (Prio p a) is exported to allow usage of distinct keys and priority values.
Min-queues and max queues are separated the following way:

Data.PQueue.Min exports the type MinQueue.
Data.PQueue.Max exports the type MaxQueue. (This is implemented as a wrapper around MinQueue.) The method names are the same as Data.PQueue.Min, but I think it's acceptable to force qualified imports when using both a max-queue and a min-queue.
Data.PQueue adds the alias type PQueue = MinQueue, so that the "default" behavior is a min-queue.

These design decisions seem to be sufficient to handle most traditional uses for priority queues. In particular, this approach offers a superset of the functionality offered by Java's built-in priority queue implementation, which makes the same design decisions, but of course, is all imperative and yucky! (Also, it offers inferior asymptotics, heh.)

I'm really satisfied with the patch as-is, modulo maybe tinkering with the code style a little. I'm also working on an article for TMR on priority queues in Haskell, some of the different structures we considered, and particularly the new more-type-safe implementation I came up with for binomial heaps in the writing of this implementation.

Anyway, discuss, complain, et cetera.

Louis Wasserman
wasserman.louis@gmail.com
http://profiles.google.com/wasserman.louis