優先度キュー とは？

普通のキューは「先に並んだ人が先に出る」先入れ先出し（FIFO）だよね。優先度キューは「優先度が高い人が先に出る」仕組みなんだ。病院の救急外来をイメージするとわかりやすいよ。軽い風邪の人より、重症の人が先に診てもらえるでしょ？

内部では「ヒープ」というデータ構造を使うことが多いよ。二分ヒープなら、要素を追加するのも一番優先度が高い要素を取り出すのもO(log n)で済むんだ。1000個の要素があっても、たった10回くらいの比較で処理できるってことだね。

たとえばOSのタスクスケジューリング。CPUの時間をどのプロセスに割り当てるか決めるときに、優先度キューで管理しているよ。あとはカーナビの最短経路計算（ダイクストラ法）でも使われているんだ。「次に調べるべき最も近い地点」を効率よく取り出せるからね。

Pythonなら heapq モジュール、Javaなら PriorityQueue クラス、C++なら priority_queue が標準で使えるよ。ほとんどの言語で用意されているから、自分でヒープを実装する必要はないんだ。

注意点は「同じ優先度の要素の順番は保証されない」ことだね。同じ優先度のタスクの順番も大事なら、挿入順をタイブレーカーとして持たせる工夫が必要だよ。あと、優先度キューは途中の要素を検索するのは苦手で、O(n)かかる点も覚えておくといいね。

フィボナッチヒープを使うと、優先度の更新（decrease-key）がO(1)の償却計算量になるよ。理論的にはダイクストラ法の計算量が改善されるんだ。ただ実装が複雑で定数倍が大きいから、実務では二分ヒープで十分なことが多いね。