Hello, I have uploaded a small benchmark to the ticket.
What do people think of the following?
Put pairing heaps (by far the fastest implementation so far, nearly 2.3x faster than binomial heaps) into containers. Launch packages containing high-quality priority search queues and real-time-ish binomial queues. (The binomial queue implementation guarantees that deleteMin has worst-case time O(log n), while pairing heaps have worst-case O(n). For people with real-time speed needs, this is relevant.) Endorse these packages in the documentation in Data.PQueue, for people with these specialized needs.
I think PQueue in containers should work in a persistent setting, which pairing heaps do not. That is why I put lazy pairing heaps in the benchmark. This variant is from Okasaki's book Purely Functional Data Structures and is _conjectured_ (and believed, at least by Okasaki and me :) to have same amortized bounds in persistent setting. Personally I would put lazy pairing heaps to the containers (beware, the current implementation has to be yet worked if we agree). If not, I would use binomial heaps or maybe benchmark leftist heaps. Have a nice day, Milan