I'm not sure about some of that. Imperative queues sometimes offer
O(1) decreaseKey and O(lg n) delete by storing pointers to elements in
a priority queue. The usual purely functional PQs can only offer O(n)
decreaseKey and O(n) delete. Purely functional PSQs can offer O(lg n)
decreaseKey and O(lg n) delete.
Minimum spanning tree is a common application for PQs that makes good
use of decreaseKey.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.
Why not use Okasaki & Brodal's "Optimal Purely Functional PriorityQueues"? They offer worst case:* O(1) union, findMin, and insert* O(lg n) deleteMinThe primary reason that we don't use this implementation is, quoting from the paper you yourself linked to,Our data structure is reasonably efficient in practice;
however, there are several competing data structures that, although
not asymptotically optimal, are somewhat faster than ours in practice.Hence, our work is primarily of theoretical interest.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.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.