優先度キューとは（全体像）
優先度キューは、取り出す順番を「優先度」で決めるキューのこと。ふつうのキュー（行列）は「先に並んだ順（FIFO）」で取り出すが、優先度キューはいちばん優先度が高いものから取り出す。
身近な例は、病院の救急。受付した順ではなく、重症の人から先に治療する。これが優先度キューの考え方だ。
主な操作は2つ。
- 追加（insert） … 要素を入れる。
- 取り出し（extract） … いちばん優先度が高い（または低い）ものを取り出す。
並んだ順ではなく優先度順、というのがふつうのキューとの決定的な違いだ。
詳しく：FIFOとの違いとヒープ実装だけ覚えれば戦える
ここが記事の心臓部。まずはふつうのキューとの違い。
ふつうのキューと優先度キュー
| ふつうのキュー | 優先度キュー | |
|---|---|---|
| 取り出す順 | 先に入れた順（FIFO） | 優先度が高い順 |
| イメージ | お店の行列 | 救急処置（重症から） |
ここがいちばん大事。優先度キューはFIFO（先入れ先出し）ではない。並んだ順を無視して、優先度の高いものを先に出す。
次に、実装と速さ。
ヒープによる実装
| 項目 | 内容 |
|---|---|
| 標準の実装 | ヒープ（親が子より大きい／小さい完全二分木） |
| 追加（insert） | O(log n) |
| 取り出し（extract） | O(log n) |
優先度キューはヒープで実装するのが標準。ヒープは根に最大（最小）が来るので、「いちばん優先度が高いものを取り出す」のと相性がよく、追加も取り出しもO(log n)で速い。つまり、ヒープの「根に最優先が来る」性質が、優先度キューにそのまま生きる、というわけだね。
注意点として、「ヒープ＝優先度キュー」ではない。ヒープは優先度キューを作るための実装手段の1つで、両者は別の概念だ。用途は、最短経路のダイクストラ法、ゲームAIの**A*探索、OSの処理の優先順位づけ**など。
わかりやすく言い換えると
要するに、優先度キューは「救急の処置室」だ。
①ふつうのキュー（FIFO） … 受付した順に呼ぶ（行列と同じ）
②優先度キュー … 受付の順ではなく、重症の人から呼ぶ（優先度が高い順）
中のしくみ（実装）にはヒープを使う。ヒープは頂点にいちばん優先度が高いものが来るので、「次に呼ぶ人」をすぐ取り出せる。だから救急のように「緊急度の高い順にさばく」処理が速くできる、というわけだね。
試験のツボ
🔴 一番出る：FIFOとの違い
①優先度キューは優先度が高い順に取り出す
②ふつうのキュー（FIFO・先入れ先出し）とは別もの
🔴 次に出る：ヒープ実装と速さ
①標準の実装はヒープ
②追加・取り出しはO(log n)で速い
🟡 押さえると安定：ヒープとの関係と用途
①ヒープは優先度キューの実装手段の1つ（同じものではない）
②ダイクストラ法・A*探索・処理の優先順位づけに使う
よくある間違い
①「優先度キューは先入れ先出し（FIFO）である」→ ✗ 優先度キューは優先度の高い順に取り出す。FIFOはふつうのキュー。
②「ヒープと優先度キューはまったく同じものである」→ ✗ ヒープは優先度キューを作る実装手段の1つ。両者は別の概念。
③「優先度キューの取り出しはO(n)で遅い」→ ✗ ヒープで実装すれば、取り出しはO(log n)で速い。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（FIFOとの違い）
優先度キューに関する次の記述のうち、正しいものはどれか。
- 優先度キューは先に入れた順（FIFO）に取り出す、ふつうのキューと同じものだ
- 優先度キューは並んだ順ではなく、優先度が高いものから取り出すキューである
- 優先度キューは後に入れた順（LIFO）に取り出す、スタックと同じものである
- 優先度キューは取り出す順番がランダムで、毎回どれが出るか分からない
解答は 2 だよ。
優先度キューは並んだ順ではなく、優先度が高いものから取り出すんだ。救急処置で重症の人から治療するイメージだね。ふつうのキュー（FIFO）とは別ものだよ。
選択肢1は「FIFOと同じ」が誤り。選択肢3は「LIFO・スタックと同じ」が誤り。選択肢4は「ランダム」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | FIFOではなく優先度順 |
| 2 | ✓ | 優先度が高い順に取り出す |
| 3 | ✗ | LIFOはスタック |
| 4 | ✗ | ランダムではなく優先度順 |
オリジナル問題2（ヒープ実装）
優先度キューの実装に関する次の記述のうち、正しいものはどれか。
- 優先度キューは並べ替えが必要なので、取り出しは必ずO(n²)で遅くなる
- 優先度キューは実装できないため、理論の中だけに存在するものである
- 優先度キューはヒープでは実装できず、配列の先頭だけで管理するものだ
- 優先度キューはヒープで実装し、追加も取り出しもO(log n)だ
解答は 4 だよ。
優先度キューはヒープで実装するのが標準で、追加も取り出しもO(log n)で速いんだ。ヒープは根に優先度が高いものが来るから、相性がいいんだよ。
選択肢1は「O(n²)で遅い」が誤り。選択肢2は「実装できない」が誤り。選択肢3は「ヒープで実装できない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | ヒープでO(log n) |
| 2 | ✗ | 実装できて広く使われる |
| 3 | ✗ | ヒープで実装するのが標準 |
| 4 | ✓ | ヒープ実装・O(log n) |
オリジナル問題3（ヒープとの関係）
優先度キューとヒープの関係に関する次の記述のうち、正しいものはどれか。
- ヒープと優先度キューはまったく同じもので、区別する必要はないものである
- 優先度キューはどこにも使われず、実用とは無関係な概念のことである
- ヒープは優先度キューを作る実装手段の1つで、ダイクストラ法で使われる
- ヒープは優先度キューとは無関係で、優先度キューには使えないものである
解答は 3 だよ。
ヒープは優先度キューを作る実装手段の1つで、優先度キューは**ダイクストラ法やA*探索**などで使われるんだ。「ヒープ＝優先度キュー」ではない、ってところがポイントだよ。
選択肢1は「まったく同じ」が誤り。選択肢2は「使われない」が誤り。選択肢4は「無関係・使えない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 別の概念（実装と抽象） |
| 2 | ✗ | ダイクストラ等で使われる |
| 3 | ✓ | ヒープは実装手段・ダイクストラで活躍 |
| 4 | ✗ | ヒープで実装できる |
まとめ
押さえどころ
- 🔴 FIFOとの違い ＝ 優先度キューは優先度が高い順に取り出す（FIFO＝ふつうのキューとは別）。
- 🔴 ヒープ実装と速さ ＝ 標準はヒープ実装。追加・取り出しはO(log n)で速い。
- 🟡 ヒープとの関係と用途 ＝ ヒープは実装手段の1つ。ダイクストラ法・A*探索などで使う。
次に学ぶ
- 木構造・ヒープ ── 優先度キューの土台になるヒープのしくみ。根に最大（最小）が来る性質がそのまま生きる。
- スタック・キュー ── ふつうのキュー（FIFO）との違いを押さえる記事。優先度キューとの対比で理解が深まる。
執筆: SikakuQuest編集部