Pythonのheapqをmax heapとして利用する方法

Pythonの優先度付きキューであるheapqはmin heapです。そのためheappop()すると、最小値がポップされます。max heapとして、最大値をポップしたい場合には、正負反転したリストをheapify()して利用するのが簡単な方法です。

import heapq

def test_heapq_maxheap():
    A = [1, 6, 8, 0, -1]
    A = [-1 * a for a in A]
    heapq.heapify(A)
    v = -1 * heapq.heappop(A)
    assert v == 8

これで、min heap（標準）とmax heapを状況に応じて使い分けられます。