Proposal: priority queues in containers

[Jim Apple]

> Since priority search queues are actually much more natural in imperative
> languages than in functional languages -- since we can maintain pointers to
> the node associated with each key -- I think it makes even less sense for
> Haskell to use PSQueues in containers.  I think it's fair to say that most
> algorithms which need it only really require priority queues, and that it
> makes sense to provide for that majority in containers, though we might
> consider recommending the PSQueue package to programmers who need the full
> power of priority search queues.

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.