木構造・ヒープとは（全体像）
ヒープは、木構造（親と子の階層）に「親子の大小ルール」を加えたデータ構造のこと。土台は完全二分木（上の段からすき間なく詰まった木）で、そこに次のルールを足す。
- 最大ヒープ … どの親も、子以上の値（だからいちばん大きい値が根に来る）。
- 最小ヒープ … どの親も、子以下の値（だからいちばん小さい値が根に来る）。
ポイントは、全体を並べ替えなくても、根を見るだけで最大（最小）が分かること。だから「いちばん大きい（小さい）ものをすぐ取り出したい」場面で活躍する。なお、ヒープは配列でも実装できる（木の形をそのまま配列に並べる）。
詳しく：最大・最小ヒープとO(log n)だけ覚えれば戦える
ここが記事の心臓部。まずは2タイプの違い。
最大ヒープと最小ヒープ
| 最大ヒープ | 最小ヒープ | |
|---|---|---|
| 親子のルール | 親 ≧ 子 | 親 ≦ 子 |
| 根に来るもの | 最大値 | 最小値 |
名前に注意。「最小ヒープ」は根が最小値（最大ではない）。名前と根に来るものが一致している、と覚えると取り違えない。
次に、よく問われる操作の速さ。
ヒープの操作と計算量
| 操作 | 速さ |
|---|---|
| 根（最大/最小）を見る | O(1)（一発） |
| 要素を追加（挿入） | O(log n) |
| 根を取り出す | O(log n) |
根を見るだけなら一発（O(1)）。追加や取り出しのあとは、ルール（親子の大小）を保つために少し並べ直すが、それでもO(log n)で速い。全部を並べ替えるO(n log n)より、必要なものだけ速く出せるのが強みだ。
なお、ヒープはふつうの木（ツリー）そのものではなく、完全二分木に大小ルールを足した特別な形。「木＝ヒープ」ではない点に注意。用途は、次に学ぶ優先度キューや、ヒープソートなど。
わかりやすく言い換えると
要するに、ヒープは「トーナメント表のような、いちばん強いのが上に来る木」だ。
①最大ヒープ … 各対戦で強いほうが上にいく。だから頂点（根）にいちばん強い（大きい）ものが来る
②最小ヒープ … ルールを逆にすれば、頂点にいちばん小さいものが来る
全選手を順位づけしなくても、頂点を見れば優勝者（最大・最小）が一発で分かる。だから「最大（最小）をすぐ取り出す」のが得意、というわけだね。
試験のツボ
🔴 一番出る：最大ヒープと最小ヒープ
①最大ヒープ＝親が子以上で、根が最大値
②最小ヒープ＝親が子以下で、根が最小値（名前どおり）
🔴 次に出る：操作の速さ
①根（最大/最小）を見るのはO(1)
②挿入・取り出しはO(log n)で速い
🟡 押さえると安定：土台と用途
①土台は完全二分木（木そのものではなく特別な形）
②配列で実装でき、優先度キューやヒープソートに使う
よくある間違い
①「最小ヒープは根に最大値が来る」→ ✗ 最小ヒープは根が最小値。名前どおり。最大値が根なのは最大ヒープ。
②「ヒープはふつうの木（ツリー）と同じものである」→ ✗ ヒープは完全二分木に親子の大小ルールを加えた特別な形。
③「ヒープの挿入や取り出しはO(n)で遅い」→ ✗ 挿入も取り出しもO(log n)で速い。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（最大・最小ヒープ）
ヒープに関する次の記述のうち、正しいものはどれか。
- 最大ヒープは根に最小値が来て、最小ヒープは根に最大値が来るものである
- 最大ヒープは根に最大値が来て、最小ヒープは根に最小値が来るものである
- 最大ヒープも最小ヒープも、根には必ず中くらいの値が来るものである
- 最大ヒープも最小ヒープも、根に来る値は毎回ランダムに変わるものだ
解答は 2 だよ。
最大ヒープは根に最大値、最小ヒープは根に最小値が来るんだ。名前と根に来るものが一致しているから、そこで覚えてね。
選択肢1は最大と最小が逆。選択肢3は「中くらいの値」が誤り。選択肢4は「ランダム」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 最大と最小が逆 |
| 2 | ✓ | 最大ヒープ＝根が最大・最小ヒープ＝根が最小 |
| 3 | ✗ | 根は最大または最小 |
| 4 | ✗ | ランダムではない |
オリジナル問題2（操作の速さ）
ヒープの操作の速さに関する次の記述のうち、正しいものはどれか。
- ヒープの挿入や取り出しはO(n²)で、データが増えると急激に遅くなる
- ヒープでは根を見ることすらできず、毎回すべてを並べ替える必要がある
- ヒープの挿入や取り出しはO(n)で、配列の先頭から探すのと変わらない
- 根を見るのはO(1)、挿入や取り出しはO(log n)で速く行える
解答は 4 だよ。
ヒープは根を見るのはO(1)（一発）、挿入や取り出しはO(log n)で速いんだ。全部を並べ替えなくても、最大（最小）をすぐ出せるのが強みだよ。
選択肢1は「O(n²)」が誤り。選択肢2は「根を見られない」が誤り。選択肢3は「O(n)」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | O(log n)で速い |
| 2 | ✗ | 根はO(1)で見られる |
| 3 | ✗ | O(log n)で線形探索より速い |
| 4 | ✓ | 根はO(1)・挿入取り出しはO(log n) |
オリジナル問題3（土台と位置づけ）
ヒープの土台や位置づけに関する次の記述のうち、正しいものはどれか。
- ヒープは完全二分木に親子の大小ルールを加えた特別な形のデータ構造だ
- ヒープはふつうの木とまったく同じもので、特別なルールは持たないものである
- ヒープは木とは無関係の、一列に並んだだけのデータ構造のことである
- ヒープは親子の大小ルールを持たず、値の並び方は自由なものとされている
解答は 1 だよ。
ヒープは完全二分木に親子の大小ルール（親が子より大きい／小さい）を加えた特別な形なんだ。「木＝ヒープ」ではない、というところがポイントだよ。
選択肢2は「ふつうの木と同じ」が誤り。選択肢3は「木と無関係・一列」が誤り。選択肢4は「大小ルールを持たない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 完全二分木＋親子の大小ルール |
| 2 | ✗ | 特別なルールを持つ |
| 3 | ✗ | 木構造の一種 |
| 4 | ✗ | 親子の大小ルールがある |
まとめ
押さえどころ
- 🔴 最大・最小ヒープ ＝ 最大ヒープは根が最大値、最小ヒープは根が最小値（名前どおり）。
- 🔴 操作の速さ ＝ 根を見るのはO(1)、挿入・取り出しはO(log n)で速い。
- 🟡 土台と用途 ＝ 完全二分木＋親子の大小ルールの特別な形。配列で実装し、優先度キューやヒープソートに使う。
次に学ぶ
- 優先度キュー（ヒープ実装） ── ヒープを使って「優先度の高いものから取り出す」しくみ。ヒープの使いどころが具体的になる。
- 木構造・逆ポーランド記法 ── 木の基本（節点・枝・走査）を押さえる記事。ヒープの土台になる木構造が深まる。
執筆: SikakuQuest編集部