+1 -- I recently did a short presentation on Big O notation and Python
containers, and heapq looked remarkably ugly.
Another issue with heapq is that it does not support modifying the priority of an existing element (usually called the "decrease_key" operation in textbooks). The hard part of incrementing decrease_key is that somehow the object in the heap needs to know its current position, else you have to do an expensive linear search to find the object's current position.
I've implemented a couple of heaps for Python over the years:
If you don't care about altering the priority, then the interface is more or less like Facundo described.
To keep track of the positions, insert operations return a wrapper around each object. The user needs to keep track of the wrapper and pass it to the adjust_key() method if they want to change the priority of the object later.
Looks, act, and quacks like a dict/MutableMapping, except popitem() returns the item with the lowest value instead of a random item. Also, there's a peekitem() method to examine that item without removing it. Since the interface is familiar, it's super-easy to use without having to look up the names of the methods whenever you need to use a heap.
The downside is that you can't add the same element into the heap twice (just like you can't have the same key in a dictionary twice). Personally I've only inserted the same element more than once when doing toy examples with integers, so for me at least that's no great loss. ;-)