優先度付きキューとは？ゆうせんどつききゅー
優先度付きキューとは、各データに優先度を持たせ、取り出すときは投入順ではなく優先度が最も高いものから出るデータ構造。ヒープを用いると、挿入も取り出しもO(log n)で実現できる。ダイクストラ法やタスクスケジューリングの実装に使われる。
最終更新：2026-10-10
ITパスポートを最短で暗記・合格する →具体例
優先度3のジョブA、優先度1のジョブB、優先度2のジョブCをこの順に入れても、優先度が高い順に取り出す設定なら、出てくるのはA→C→Bとなる。ヒープで実装すれば、根を取り出して末尾要素を根へ移し、木の高さぶん整え直すだけで済む。
試験での引っ掛け
「キュー」と付くがFIFOではない点が最大の落とし穴。また同じ優先度どうしの順序は保証されないのが一般的で、投入順を保ちたいなら優先度に投入時刻を組み合わせるなどの工夫が要る。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。