ヒープとは？2分木で見ると一気に分かる！【基本情報技術者試験 科目B】

🎯 この記事でわかること

---

• ヒープとは何か
• 配列と2分木の対応
• 親 = i ÷ 2 の意味
• 最大ヒープの作り方
• 基本情報技術者試験での解き方

---

---

🌳 ヒープとは？

ヒープとは、

親の値が子の値以上（または以下）になるようにした2分木

のことです。

今回は 最大ヒープ を扱います。

---

最大ヒープのルール

親 ≥ 子

---

📝 配列と2分木の対応

配列：

{9, 8, 6, 2, 4}

2分木：

---

配列番号との対応

配列番号	値	木の位置
1	9	根（いちばん上）
2	8	左の子
3	6	右の子
4	2	左の子の左
5	4	左の子の右

---

🎯 親 = i ÷ 2 の意味

配列の i 番目の要素の親は、

i を 2 で割った商（整数部分）

で求められます。

---

例

i = 5

5 ÷ 2 = 2

→ heap[5] の親は heap[2]

i = 3

3 ÷ 2 = 1

→ heap[3] の親は heap[1]

---

i = 1 の場合

1番目は根なので、親はありません。

1 ÷ 2 = 0

となりますが、実際には参照しません。

---

🎯 覚えておく公式

親

parent = i ÷ 2 の商

左の子

2 × i

右の子

2 × i + 1

---

💻 例題

次のデータを順番に最大ヒープに追加します。

data = {4, 9, 6, 2, 8}

---

📝 順番に追加してみよう

① 4 を追加

{4}

---

② 9 を追加

{4, 9}

9 > 4 なので交換。

{9, 4}

---

③ 6 を追加

{9, 4, 6}

6 < 9 なのでそのまま。

---

④ 2 を追加

{9, 4, 6, 2}

2 < 4 なのでそのまま。

---

⑤ 8 を追加

{9, 4, 6, 2, 8}

8 > 4 なので交換。

{9, 8, 6, 2, 4}

8 < 9 なので終了。

---

🌳 最終的な2分木

---

🎉 最終結果

{9, 8, 6, 2, 4}

---

🧠 解き方のコツ

1. 配列の末尾に追加する
2. 親 (i ÷ 2) を求める
3. 子の方が大きければ交換
4. 根 (i = 1) に到達するまで繰り返す

---

🎯 練習問題

次のデータを最大ヒープにすると？

{7, 3, 12, 5, 9}

🌳 順番に追加してみよう

① 7 を追加

{7}

---

② 3 を追加

{7, 3}

3 < 7 なのでそのまま。

---

③ 12 を追加

{7, 3, 12}

12 > 7 なので交換。

{12, 3, 7}

---

④ 5 を追加

{12, 3, 7, 5}

5 > 3 なので交換。

{12, 5, 7, 3}

---

⑤ 9 を追加

{12, 5, 7, 3, 9}

9 > 5 なので交換。

{12, 9, 7, 3, 5}

9 < 12 なので終了。

---

🌳 最終的な2分木

---

🎯 最終結果

{12, 9, 7, 3, 5}

---

🎉 まとめ

• ヒープは親と子の大小関係を持つ2分木
• 配列を木にすると理解しやすい
• 親の位置は i ÷ 2
• 親より大きければ上に移動
• 1番目（根）には親がない

---

💬 最後に

ヒープの問題は、配列だけを見ると難しく感じます。

でも、

2分木にすると、何が起きているのか一気に分かります！

基本情報技術者試験でも頻出なので、ぜひ「木に変換して考える」クセをつけてみてね✨