はじめに
Pythonで優先度付きキューの挙動で謎な部分があり調べてみた。
不可解な挙動
こちらを参考に、Pythonで優先度付きキューが調べていたところ、heapqライブラリで実現が可能とのこと。
上記リンク先にでは、heapqの使用例として以下の通り記載されていた。
#引用元：https://qiita.com/ell/items/fe52a9eb9499b7060ed6
import heapq # heapqライブラリのimport
a = [1, 6, 8, 0, -1]
heapq.heapify(a) # リストを優先度付きキューへ
print(a)
# 出力: [-1, 0, 8, 1, 6] (優先度付きキューとなった a)
なぜ出力がこの並び（[-1, 0, 8, 1, 6] ）なのか？
誰も興味無さそうな疑問が湧いてきた（昇順を期待してたので）。
理由：リストの要素をヒープキューアルゴリズムでソートしているため
Pythonでは、優先度付きキューをリストで表現している様であるが、
python documentによると、ヒープキューアルゴリズムでリストの内容を並べ替えしているとのこと。
こちらのヒープの説明サイトにて、ヒープのアルゴリズムの説明が詳しく記載されているが、
木構造をリストで表現できるとのこと（親ノードのリストインデックスをiとすると、子の左ノードが2*i、右ノードが2*i+1)。
親子関係が成立する様に、リスト内の要素を入れ替えすると、上記の出力が得られた。
ヒープキューアルゴリズムによるソートの流れ
※詳しいアルゴリズムはこちらを参照
ヒープの条件：各ノードがその子ノードより小さいか等しい
初期配列：[1, 6, 8, 0, -1]
