If you're interested in adding priority queues to containers, shameless plug: I've got a good implementation of pairing heaps in http://hackage.haskell.org/package/queuelike. It's a bit obfuscated right now, but I'd definitely be interested in producing something that's actually readable and usable enough to be put into containers...