優先度付きキューとヒープとは？
優先度付きキューとヒープとは、優先度付きキューは、格納された要素のうち優先度が最も高い（または低い）ものを常に先に取り出せるデータ構造。ヒープは、この優先度付きキューを効率よく実現するための木構造（二分木）で、親の値が常に子の値以上（または以下）になるよう並べる規則（ヒープ条件）を持つ。要素の追加・取り出しがO(log n)で行えるため、ヒープソートにも応用される。
ゆうせんどつききゅーとひーぷ
優先度付きキューとヒープの意味
優先度付きキューは、格納された要素のうち優先度が最も高い（または低い）ものを常に先に取り出せるデータ構造。ヒープは、この優先度付きキューを効率よく実現するための木構造（二分木）で、親の値が常に子の値以上（または以下）になるよう並べる規則（ヒープ条件）を持つ。要素の追加・取り出しがO(log n)で行えるため、ヒープソートにも応用される。
優先度付きキューとヒープの具体例
タスクの優先度に応じて処理順を決める処理系では、優先度が最も高いタスクを常に高速に取り出せるヒープを使ったキューが使われることが多い。
優先度付きキューとヒープは試験でどう引っ掛けられる？
優先度付きキューは名前に「キュー」と付くが、取り出し順は到着順（FIFO）ではなく優先度順で、通常のキューやスタック（LIFO）とは別物。またヒープ条件が保証するのは「親が子より大きい（小さい）」ことだけで、全体が整列されているわけではない——根が最大（最小）と分かるだけで、2番目に大きい要素の位置は一意に定まらない。二分探索木のように「左が小さく右が大きい」という左右の大小関係も持たない。なお記憶領域の動的確保に使うヒープ領域とは同名の別概念。
優先度付きキューとヒープと関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。