Okay, here's my current plan:  I think I'm going to withdraw the ticket for containers, and launch a package to be included in a future release of the Haskell Platform.  

First off, I'd like to know what the procedure is for adding something to the Platform.  I haven't been able to find a mailing list dedicated to it, so I don't know where it should be discussed.  (In all likelihood, I'm missing some obvious link on either Trac or HaskellWiki or something...)

First, people should look at my current setup, and complain at me about the design.  Haddock documentation is here, though I've only so far documented the minimum-queue variants; in general, I aimed to use the same function names used by Data.Map and Data.Set wherever possible, so "extract," "top," and "delete" have been replaced by the function names used for the analogous methods in Data.Map and Data.Set.  

Probably the single aspect of the design I'm least happy about is how I distinguish between the priority queues that distinguish a key and an element, and those which don't.  Currently, the Data.Map-style key/element version is named MinPQueue k a, and lives in the module Data.PQueue.Prio.Min, and the Data.Set-style version is named MinQueue a, and lives in the module Data.PQueue.Min.  Can anybody think of better names for these things?

Finally, I'm not going to consider any more alternative implementations at this point.  My implementation has performed outstandingly on benchmarks, and has beaten a number of competitors.  If someone believes that they have a superior implementation, they should email me off-list, and perhaps a later version of the package will be based on a different implementation, but for the moment I'm sticking to the type-magical binomial heap implementation.