【ゆうせんどきゅー】

優先度キュー とは?

💡 行列に並んでも、VIPは先に通される特別なキュー
📌 このページのポイント
通常のキュー vs 優先度キュー 通常のキュー(FIFO) A (1番) B (2番) C (3番) 並んだ順に出る A B C → A → B → C の順 優先度キュー A 優先度:低 B 優先度:高 ★★★ C 優先度:中 ★★ 優先度順に出る B (高) C (中) A (低) → B → C → A の順
通常のキューと優先度キューの取り出し順の違い
ひよこ ひよこ

優先度キューって普通のキューと何が違うの?

ペンギン先生 ペンギン先生

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

ひよこ ひよこ

なるほど!中身はどうなってるの?

ペンギン先生 ペンギン先生

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

ひよこ ひよこ

速いんだね!具体的にはどこで使われてるの?

ペンギン先生 ペンギン先生

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

ひよこ ひよこ

カーナビにも使われてるんだね!プログラミングではどうやって使うの?

ペンギン先生 ペンギン先生

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

ひよこ ひよこ

便利だね!何か気をつけることはあるの?

ペンギン先生 ペンギン先生

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

ひよこ ひよこ

万能じゃないんだね!もっと発展的な種類もあるの?

ペンギン先生 ペンギン先生

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

ペンギン
まとめ:ざっくりこれだけ覚えればOK!
「優先度キュー」って出てきたら「重要なものから先に取り出せるデータ構造」と思えばだいたいOK!
📖 おまけ:英語の意味
「Priority Queue」 = 優先度付きキュー
💬 「Priority(優先度)」+「Queue(行列・待ち行列)」。大事なものから処理するって意味だよ
← 用語集にもどる