I realize this request is closed, but I hope people will still be reading this comment, and can perhaps either reopen it or submit a new request.  I don't know how to submit a new request myself.
...

I'd like to see (key=) capability somehow, without degrading performance of time-critical applications.
I've got some ideas for your consideration, if you please.

1. Make the heapq into a heap class.  It would be more natural (for me, anyway) to push/pop using the heap's methods, rather than calling a function in the heap package and having to specify the heap list as well.

A heap class in C could outperform current heapq with lists by storing the member objects in an internal array.

This would also solve the issue of having the user switch comparison methods in the middle of things.  The comparison method would be specified when the heap is constructed.  It could be changed later, at the expense of resorting the heap.  I suggest the comparison method parameters be the same as for .sort () and sorted ().

By default, the heap class would directly compare elements using __lt__, and so the performance would be as good, or slightly better, than the current heapq package functions.

2. In my own use case, I have to define __lt__ for the objects in my heapq by comparing the _keys_ of the two items.  So push/pop wind up calling the key function many times anyway.  The heap push/pop themselves could do this same work probably a bit faster in C code than would calling my own __lt__ method.

3. Performance could be improved when there is a key function by having the heap store both the heap elements and their keys.  I believe a C implementation could benefit by storing key and value objects next to each other in the internal array.

4. I'd be happy to submit a reference implementation, only I don't have time to do that right now, sorry.  I'm sure someone else would be up to the challenge.