Implementing a max-heap with heapq

Question

Accepted Answer

Python's heapq always maintains the smallest element at the top. The standard workaround is to push `-x` instead of `x`. When you pop, the smallest negative value corresponds to the largest original value - so negate it again on the way out. This idiom is universally understood by Python developers and comes up constantly in interview problems involving the k-th largest element or a running maximum.