はじめに

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とすると、子の左ノードが2i、右ノードが2i+1)。
親子関係が成立する様に、リスト内の要素を入れ替えすると、上記の出力が得られた。

ヒープキューアルゴリズムによるソートの流れ

※詳しいアルゴリズムはこちらを参照

ヒープの条件：各ノードがその子ノードより小さいか等しい
初期配列：[1, 6, 8, 0, -1]