優先度付きキューとは？

優先度付きキューの意味

各データに優先度を持たせ、取り出すときは投入順ではなく優先度が最も高いものから出るデータ構造。ヒープを用いると、挿入も取り出しもO(log n)で実現できる。ダイクストラ法やタスクスケジューリングの実装に使われる。

優先度付きキューの具体例

優先度3のジョブA、優先度1のジョブB、優先度2のジョブCをこの順に入れても、優先度が高い順に取り出す設定なら、出てくるのはA→C→Bとなる。ヒープで実装すれば、根を取り出して末尾要素を根へ移し、木の高さぶん整え直すだけで済む。

優先度付きキューは試験でどう引っ掛けられる？

「キュー」と付くがFIFOではない点が最大の落とし穴。また同じ優先度どうしの順序は保証されないのが一般的で、投入順を保ちたいなら優先度に投入時刻を組み合わせるなどの工夫が要る。

優先度付きキューと関連する用語

• ヒープ
• キュー
• ダイクストラ法

優先度付きキューが出た過去問

• 次の記述中の に入れる正しい答えを、解答群の中から選べ。 優先度付きキューを操作するプログラムである。優先度付きキューとは扱う要素に優先度を付けたキューであり、…

  正解："A", "C", "D", "D"

  要点：優先度付きキューは優先度順、同順位は先入れ先出し

  優先度は数値が小さいほど高く、同じ優先度なら先に入れたものが先に出ます。前半でA(1)とB(2)が取り出され、次にD(3)とB(2)を追加した状態から、優先度2のC、続いて後から入れたB(2)が取り出されます。残ったD(3)とD(3)にC(2)とA(1)を加えて最後まで出力すると、A、C、D、Dの順になります。

  出典：令和4年度 s 基本情報技術者試験 kamokuB 問8（IPA）