I'd very much like to see the current heapq replaced with a different interface in time for 2.3. I believe that an opaque object is better, since it allows more flexibility later.
I'm quite pleased with the version already in CVS. It is a small masterpiece of exposition, sophistication, simplicity, and speed. A class based interface is not necessary for every algorithm.
For the other approaches, what might be useful is to define an API and leave it that. The various implementations can be maintained on Cookbook pages, the Vaults of Parnassus, or an SF project.
The min/max heap and fibonacci heaps are a great idea. Nice work.