heapq library in Python only supports min-heaps and is implemented in pure python, which makes it quite slow. Is there a decent heap library the supports both min-heaps and max-heaps and is written in C?
Heap functionality is so tiny, it should be inlined whenever possible. In python, this means copy&paste (I'm not aware of Python automatically inlining small functions, like Java does).
Whatever library you use, it will come at a non-neglibile invocation overhead. More than just putting the code (specific for your problem) inline. To really improve things, convert your code to Cython then.