要点

• python の heap はデータ構造ではなくアルゴリズムとして動作する
• heapq の要素は小さいものから取り出される

heapq の使用例

heap への要素の追加は heapq.heappush(list, 要素)。 heap からの要素の取り出しは heapq.heappop(list)。 heapq.heappop は heap の要素を小さいものから取り出します。

import heapq

q = []
heapq.heapify(q)

heapq.heappush(q, 2)
heapq.heappush(q, 1)
heapq.heappush(q, 3)

while q:
    u = heapq.heappop(q)
    print(u)
"""
output is
1
2
3
"""

heapify の行っていること

heapify は与えられたリストの要素を heap 用の順番に並べ替えます。

import heapq

q = [3, 2, 5, 1]
heapq.heapify(q)
print(q)  # [1, 2, 5, 3]

heap の対象とするリストが空であれば、heapify は不要です。
すでに要素の詰まっているリストに対して、heapify を行わずに pop した場合は、必ずしも最小要素は取り出されません。

import heapq

q = [3, 2, 5, 1]
# heapq.heapify(q)  # 本来は必要
print(heapq.heappop(q))  # 3 が出力される。 heap に期待する出力は 1

間違った使用例

エラーの出ない間違った使用例

heap にしたリストは pop できますが、リストの後ろから要素を取り出す動作です。
対象のリストは heap なので、当然ソートされていません。

import heapq

q = []
heapq.heapify(q)

heapq.heappush(q, 2)
heapq.heappush(q, 1)
heapq.heappush(q, 3)

u = q.pop()  # ここが間違い 正しくは u = heapq.heappop(q)
print(u)  # 3 が出力される

エラーの出る間違った使用例

heapq はオブジェクト指向ではありません。
したがって、 q = heapq.heapify([]) とすると q = None となります。
heapq.heappush() の第一引数はリストなので、None を渡している下のプログラムはエラーします。

import heapq

q = heapq.heapify([])  # ここが間違い
heapq.heappush(q, 1)

"""
Exception has occurred: TypeError
heap argument must be a list
"""

なぜ heapq はデータ構造を提供していないのか?

やはりこのオブジェクト指向ではない設計に疑問を持つ方はいるようです。
例 1
例 2

なぜこんな実装にしたのか納得する理由は見つかりませんが、heap は sort できないから という主張は見つかりました。
リストや辞書のデータ構造と一貫性を持たせたいということだと理解しました。
しかし、heap をソートしたいプログラマなどいるのでしょうか？