優先度キュー とは？

普通のキューは先入れ先出し（FIFO）で、追加した順に取り出すよ。優先度キューは、決めた優先度の規則で次を選ぶ。たとえばA、B、Cの順に追加しても、Bの優先度が最も高ければBから取り出せるんだ。

規則によるよ。Pythonのheapqの通常の操作は最小値を先に取り出し、JavaのPriorityQueueも自然順序や指定した比較規則で最小となる要素を先頭にする。内部に二分ヒープを使う場合、追加や先頭の取り出しはO(log n)だよ。これは要素数に対する増え方の目安で、「1000個なら必ず10回比較」という意味ではないんだ。

優先して処理するタスクを選んだり、シミュレーションで次に起きるイベントを予定時刻順に取り出したりするよ。負の重みがないグラフの最短経路を求めるダイクストラ法でも、現在の距離が最小の候補を選ぶ実装に使う。すべてのOSやカーナビが同じ実装を使う、というわけではないんだ。

Pythonのheapqなら、リストにヒープの規則を保って追加・取り出しを行うよ。JavaならPriorityQueueに要素を追加し、pollで取り出せる。ただし内部配列やイテレーターが取り出し順に全部並んでいるとは限らない。Javaのcontainsなど、途中の要素を探す操作にはO(n)かかるものもあるんだ。

同じ優先度で追加順が保たれるかは実装によるよ。JavaのPriorityQueueでは同順位の順番は保証されないので、順番が必要なら連番などを比較規則に加える。追加済みの要素の優先度だけを書き換えるとヒープの規則を壊すことがあるため、削除して入れ直すなど、使う実装に合った更新方法を選ぼう。