ヒープはソート済みリストではない：優先度付きキューの並び順とインデックスの式
heapq や PriorityQueue を出力すると、なぜ並んでいないのか。ヒープが守る条件、0始まりの親子インデックスの式、ソート済みリストとの計算量の違い、同じ優先度の扱いを公式ドキュメントで整理します。
heapq.heapify を通したリストを出力すると、小さい順に並んでいるという予想は外れます。
import heapq
h = [5, 3, 8, 1, 9, 2]
heapq.heapify(h)
print(h) # [1, 3, 2, 5, 9, 8]
print([heapq.heappop(h) for _ in range(len(h))]) # [1, 2, 3, 5, 8, 9]コメントの出力は Python 3.14.7 で実行した結果です。正確な内部配列はこのバージョンで観察した結果であり、API の保証ではありません。API が保証するのはヒープ条件と、インデックス0に最小値の一つがあることです。
リスト自体は並んでいないのに、1つずつ取り出すと小さい順に出てきます。最小ヒープは最小値の一つがインデックス0にあることを保証し、残りの配列には親子間のヒープ条件だけを課します。
ヒープが守る条件
Python のドキュメントは最小ヒープを、比較する要素が存在するすべての k について heap[k] <= heap[2*k+1] と heap[k] <= heap[2*k+2] が成り立つリストと定義し、要素は0から数えるとしています。配列を二分木として見ると、インデックス i の子は 2*i+1 と 2*i+2、親は (i-1)//2 です。
公開されている C++ 規格ドラフトは、同じ関係を親の側から書いています。0 < i < N のすべての i で comp(a[⌊(i−1)/2⌋], a[i]) が偽ならヒープです。1始まりの教科書の式と違う点は、Python のドキュメントも触れています。
この条件が比べるのは親と子だけです。兄弟どうしや別の枝のノードどうしには決まった順序がありません。上の結果でインデックス1の3がインデックス2の2より大きくても問題ないのはそのためです。どちらも根の1の子にすぎません。逆にソート済みのリストは常にこの条件を満たすので、Python のドキュメントにあるとおり heap.sort() をしてもヒープ条件は崩れません。
走査の順序はほかの言語でも約束されない
Java の PriorityQueue のドキュメントは、iterator() と spliterator() が特定の順序で要素を走査するとは保証されないと書き、順序が必要なら Arrays.sort(pq.toArray()) を使うよう勧めています。toArray() が返す配列も順不同です。for-each で出力した結果がばらばらでも、バグではありません。
C++ の std::priority_queue では、top() は内部コンテナの front() を返し、pop() は pop_heap のあとに pop_back を行うと定義されています。既定の比較子 less を使うと条件は「親は子より小さくない」になり、先頭には最大の値が来ます。最小ヒープが既定の Python の heapq とは逆です。Python にも 3.14 で heapify_max や heappop_max などの最大ヒープ用関数が加わりました。
ソート済みリストとの違い
ソート済みリストに値を挿入するとき、位置は二分探索で見つけられます。ただし Python の bisect のドキュメントは、O(log n) の探索は O(n) の挿入処理に支配されると書いています。
公開されている C++ 規格ドラフトでは、ヒープへの追加は比較最大 log N 回、先頭の削除は最大 2 log N 回です。Java のドキュメントの実装メモも、offer・poll は O(log n)、peek は定数時間としています。一方、任意の要素を探す Java の contains と remove(Object) は線形時間です。既存のリストをヒープにする heapify は、その場で線形時間で終わります。
すべての値を順に見たいならソート、値が次々に入ってくる中で最小のものだけを繰り返し取り出したいならヒープが向いています。小さい値をいくつかだけ欲しいときの nsmallest も n が小さいときに有利です。ドキュメントは、n が大きければ sorted()、n が1なら min() のほうが効率的だとしています。
優先度が同じとき
ヒープは同じ値どうしの到着順を守りません。Java のドキュメントは、最小の要素が複数あれば先頭はそのどれかになり、どれになるかは任意だとしています。Python のドキュメントは、heapq で実装したヒープソートは sorted() と違って安定ではないと書いています。
追加した順に取り出したいなら、Python のドキュメントの案のように [優先度, 追加番号, タスク] の形で保存し、追加番号で同点を決めます。番号は重ならないので、タスクどうしを直接比べることもありません。