Pythonのheapqにリストを入れたときの挙動

競技プログラミングやっててPythonでDijkstraを実装しようとした時、heapqに("頂点名",距離)みたいなのを突っ込んで距離でソートしてほしかったのですが、その時の挙動がちょっと不安だったので確かめただけのメモ記事です。

カスタム演算子みたいなのが突っ込めるのかなぁ…とも思いましたが、そこ自作するとたいてい遅くなるのでできるだけ避けたい気持ちで調べました。

heapqの仕様というかPythonの比較演算子の仕様だとは思うんですが、せっかくなのでまとめておきます。

結論

heapqにリストを突っ込むと、
第一要素の昇順→第２要素の昇順というふうに評価される。要素同士の評価は独立に行われるっぽいので数字と文字列を混ぜても大丈夫。

要は、

[[1,4],[2,0],[0,1],[0,3]]
↓
[[0,1],[0,3],[1,4],[2,0]]

みたいな感じになります。

検証1

import heapq
import random
a = []
heapq.heapify(a)

for i in range(5):
    heapq.heappush(a,[random.randint(0,10) for i in range(2)])

while a:
    print(heapq.heappop(a))

[0, 10]
[2, 7]
[2, 7]
[2, 10]
[5, 0]

検証2

for i in range(5):
    heapq.heappush(a,[random.randint(0,10),chr(random.randint(97,97+26))])

while a:
    print(heapq.heappop(a))

[0, 'k']
[4, 'd']
[4, 'l']
[5, 'c']
[7, 'o']

以上。Pythonくんはやっぱりなんやかんやいい感じにしてくれることが多くて好きですが、たまに事故るので好きじゃないです(矛盾)