> The only hacks around that I could think of required a more complex kind of heap; e.g., restricting heap items to objects usable as dict keys, using a hidden dict to map heap items to their current index, and fiddling all the heap operations to keep that dict up to date.

Actually, this is *exactly* how I ended up thinking about this feature. I was using a separate dict to track the index at which objects are inserted in a heap, using the index to make updates to heap directly, and fixing the heap by calling heapify() every time which was slightly costly. Maybe I chose the wrong data structure for the problem, but constant time getMin() operation was crucial for me. And I didn't really care if inserts (or updates) were costlier. 

But I completely agree that it's a niche use case and I understand if we don't want to support this :)