優先度付きキューとは？ゆうせんどつききゅー
優先度付きキューとは、入れた順ではなく、優先度が最も高い要素から取り出せるデータ構造。ヒープで実装すれば挿入も取り出しもO(log n)、つまりデータ件数が増えても手間はゆるやかにしか増えない。ダイクストラ法やタスクの実行順の管理に使われる。
最終更新：2026-10-09
この語が出る過去問を解く →背景
先に入れたものから出す普通のキューでは、急ぎの用件が後から来ても列の最後尾に並ぶ。かといって毎回すべてを見て一番急ぎを探すと、件数に比例して遅くなる。最優先の1件だけをすぐ取り出せて、追加も速い構造として考えられたのがこれで、木の形にして半分ずつ絞るヒープが定番の実装になっている。
具体例
救急外来の受付が近い。到着順ではなく重症度で診る順を決めるので、後から来た重い患者が先に呼ばれる。プログラムではPythonの標準ライブラリheapqやJavaのPriorityQueueがこの構造を提供し、ダイクストラ法で「まだ確定していない中で最も近い頂点」を取り出す場面で使われる。
試験での引っ掛け
名前にキューと付くがFIFOではなく、先入れ先出しのつもりで解くと誤る。同じ優先度どうしの取り出し順は保証されないのが普通で、投入順を守りたいなら優先度に投入時刻を組み合わせる。ヒープは根が最優先なだけで、全体が整列されているわけでもない。
関連用語
出た過去問
出典：令和4年度 公開問題 基本情報技術者試験 科目B 問8（IPA）
次の記述中の に入れる正しい答えを、解答群の中から選べ。 優先度付きキューを操作するプログラムである。優先度付きキューとは扱う要素に優先度を付けたキューであり、…
正解："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の順になります。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。