Ever since Python 2.4, the heapq module has been written in C. It was only Python 2.3 which had the pure Python implementation.

I've used heapq for several of my projects, including one where I did extensive performance testing, and I haven't found it to be a problem.