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