Overall, I'm not in favor of the patch or the basic idea.  The heapq 
module is somewhat usable as-is with apps typically inserting tuples 
linking a priority level and a record.  

Also, the attached code is not yet mature, nor does it evidence 
compelling use cases or user demand.  This may make a good ASPN recipe 
but would be premature for inclusion in the standard library.

One quick comment on the API, it would be better to have just a key 
function and to drop the cmp function as Python itself has done 
throughout the language in Py3.0.

Recommend rejecting the feature request, leaving the module as clean as 
possible.  If the code is published separately (perhaps as an ASPN 
recipe or third-party module), it may yet mature and gather a fan club.