ヒープとは？

ヒープとは、全ての節について「親の値≧子の値」（最大ヒープ）または「親の値≦子の値」（最小ヒープ）が成り立つ完全二分木。根には常に最大値または最小値が来る。挿入と根の取り出しがともにO(log n)で行え、優先度付きキューやヒープソートの土台になる。

ひーぷ

基本情報技術者試験の頻出用語／テクノロジ系

ヒープの意味

全ての節について「親の値≧子の値」（最大ヒープ）または「親の値≦子の値」（最小ヒープ）が成り立つ完全二分木。根には常に最大値または最小値が来る。挿入と根の取り出しがともにO(log n)で行え、優先度付きキューやヒープソートの土台になる。

最小ヒープに新しい値を追加するときは、まず最下位レベルの左詰めの位置に置き、親と比べて小さければ交換する操作を根に向かって繰り返す。逆に根を取り出したら末尾の要素を根へ移し、小さいほうの子と比べながら下へ降ろして整え直す。

兄弟間や左右の部分木の間には順序関係が無い。したがってヒープを通りがけ順でたどっても昇順にはならない（それは二分探索木）。また「2番目に大きい値」は根の子のどちらかにあるが、3番目以降は位置が決まらない。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。