第3版　[解答]アルゴリズムイントロダクション 6-2:ヒープ条件の維持

## 1.配列A = (27,17,3,16,13,10,1,5,7,12,4,8,9,0)上でのmax-heapify(A, 3)の動作を示せ。

`max-heapify(A, 3)` の動作を説明するには、**まず A がヒープであると仮定して**、インデックス `3` 番目（1始まり）のノードを部分的に再ヒープ化する操作です。

### 🔢 前提

* 配列は1始まり（ヒープアルゴリズムの教科書通り）であると仮定します。
* `A = (nil, 27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0)`（`nil`を先頭に加えて 1-indexed に）

ここで `max-heapify(A, 3)` を呼ぶと、ノード 3（値は 3）とその子たちの間でヒープ条件を回復します。

---

### 🌲 ヒープの部分構造

ノード 3 の子は

* 左の子：`2 * 3 = 6` → A\[6] = 10
* 右の子：`2 * 3 + 1 = 7` → A\[7] = 1

最大値は `A[6] = 10`（親より大きい）なので、**A\[3] と A\[6] を交換**します。

#### 交換後：

```
A = (nil, 27, 17, 10, 16, 13, 3, 1, 5, 7, 12, 4, 8, 9, 0)
```

次に、再帰的に `max-heapify(A, 6)` を行います。

---

### max-heapify(A, 6)

* A\[6] = 3
* 左の子：12番 → A\[12] = 4
* 右の子：13番 → A\[13] = 8

最大値は A\[13] = 8 → **A\[6]とA\[13]を交換**

#### 交換後：

```
A = (nil, 27, 17, 10, 16, 13, 8, 1, 5, 7, 12, 4, 3, 9, 0)
```

次に `max-heapify(A, 13)` を行うが、子がいないので終了。

---

### ✅ 最終結果（1-indexed 表記）

```
A = (nil, 27, 17, 10, 16, 13, 8, 1, 5, 7, 12, 4, 3, 9, 0)
```

### 🟩 結果（0-indexedに戻すと）

```
A = (27, 17, 10, 16, 13, 8, 1, 5, 7, 12, 4, 3, 9, 0)
```

---

### 🧠 補足：max-heapifyの基本

`max-heapify(A, i)` は以下を実行：

1. 子ノード（2i, 2i+1）と自分自身（i）を比較
2. 最大値と交換
3. 交換した場合はその子ノードでも再帰的に max-heapify

---
以下に `max-heapify(A, 3)` の操作を図で示します。図では\*\*ヒープ木構造（完全二分木）\*\*として描き、該当ノードを強調します。

---

### 🟦 初期状態（1-indexed 配列）

```
               27
             /     \
           17       3     ← max-heapify対象
         /   \     /   \
       16   13   10   1
      / \   / \   / \
     5  7 12  4  8  9
    /
   0
```

* max-heapify(A, 3) → A\[3] = 3（子: A\[6] = 10, A\[7] = 1）
* **最大は 10（A\[6]） → A\[3] と交換**

---

### 🔁 1回目の交換（A\[3] と A\[6]）

```
               27
             /     \
           17      10
         /   \     /   \
       16   13    3     1
      / \   / \   / \
     5  7 12  4  8  9
    /
   0
```

* 次に max-heapify(A, 6) → A\[6] = 3（子: A\[12]=4, A\[13]=8）
* **最大は 8（A\[13]） → A\[6] と交換**

---

### 🔁 2回目の交換（A\[6] と A\[13]）

```
               27
             /     \
           17      10
         /   \     /   \
       16   13    8     1
      / \   / \   / \
     5  7 12  4  3  9
    /
   0
```

* A\[13] = 3 に子なし → 再帰終了

---

### ✅ 最終的な max-heapify(A, 3) の結果：

```
               27
             /     \
           17      10
         /   \     /   \
       16   13    8     1
      / \   / \   / \
     5  7 12  4  3  9
    /
   0
```

---

図のように、ヒープ条件（親 ≥ 子）を **部分木**に対して回復するのが `max-heapify` の目的です。

## 2.max-heapifyを利用してminヒープ上でmax-heapifyに対応する操作を実現する手続きmin-heapify(A,i)の疑似コードをかけ。min-heapifyの実行時間をmax-heapifyと比較せよ。

了解です。以下に `min-heapify(A, i)` の**擬似コード**とその**実行時間の比較**を示します。

---

## ✅ min-heapify(A, i) の擬似コード

これは **minヒープ（親 ≤ 子）** の条件を保つように、ノード `i` とその部分木に対して再構成する手続きです。`max-heapify` を逆にして「最小値と交換」するようにします。

```plaintext
MIN-HEAPIFY(A, i)
    l ← LEFT(i)
    r ← RIGHT(i)
    smallest ← i

    if l ≤ heap-size[A] and A[l] < A[smallest]
        smallest ← l
    if r ≤ heap-size[A] and A[r] < A[smallest]
        smallest ← r

    if smallest ≠ i
        swap A[i] ↔ A[smallest]
        MIN-HEAPIFY(A, smallest)
```

* `LEFT(i)` = `2i`
* `RIGHT(i)` = `2i + 1`

---

## 🕒 実行時間の比較

### 時間計算量

* **max-heapify**: `O(log n)`
* **min-heapify**: `O(log n)`

どちらも **完全二分木**上の操作なので、1回の `heapify` で下に最大 `log n` 回の再帰的な移動があるため、**時間計算量は同じ**です。

### 比較まとめ

| 操作名           | 条件       | 優先方向 | 計算量        |
| ------------- | -------- | ---- | ---------- |
| `max-heapify` | 親 ≥ 子を維持 | 大きい方 | `O(log n)` |
| `min-heapify` | 親 ≤ 子を維持 | 小さい方 | `O(log n)` |

---

## 🔁 補足：min-heapify はどこで使う？

* **最小値優先の優先度付きキュー**
* \*\*ヒープソート（昇順）\*\*では `min-heap` を構築し `min-heapify` を使う場合もあります。

---

## 3.要素A[i]が左右両方の子より大きい時、呼び出しmax-heapify(A,i)が与える影響を述べよ。

この問いは、`max-heapify(A, i)` を **呼び出した時点で A\[i] がすでに左右両方の子より大きい**場合、つまり **局所的にヒープ条件が満たされているとき、`max-heapify` が何をするか**を問うています。

---

## ✅ 結論

**`max-heapify(A, i)` は何も変更を行わず、再帰も発生せずに終了する。**

---

## 🔍 理由（詳細）

`max-heapify` の処理は以下の通り：

1. ノード `i` の左右の子（2i, 2i+1）と自分自身 `A[i]` を比較
2. **最大の要素が `A[i]` 自身であれば交換せず終了**
3. それ以外の場合にのみ交換し、再帰的に呼び出す

### このケースでは：

```
A[i] > A[2i] および A[i] > A[2i+1]
```

→ A\[i] は3者の中で最大 → swapも再帰も**発生しない**

---

## 🕒 時間計算量的にも

このケースでは `max-heapify` の処理時間は **Θ(1)**（定数時間）で終わる
※ 最悪では `O(log n)` だが、このように条件を満たしている場合は最短で終了する

---

## ✅ まとめ

| 条件                                 | 結果                         |
| ---------------------------------- | -------------------------- |
| `A[i] ≥ A[2i]` かつ `A[i] ≥ A[2i+1]` | `max-heapify(A, i)` は何もしない |
|                                    | 部分木はすでに max-heap を満たしている   |
| 実行時間                               | Θ(1)                       |

---

## 4. i > A.heap-size/2の時、呼び出しmax-heapify(A,i)が与える影響を述べよ。

### ✅ 問題の意図

この問いは、「`i > A.heap-size / 2`」、つまり **ノード `i` が葉ノードであるとき**に `max-heapify(A, i)` を呼び出した場合、何が起こるかを尋ねています。

---

## 🍃 葉ノードの条件

ヒープは **完全二分木**なので、\*\*葉ノードはすべて配列の後半（`i > ⌊n/2⌋`）\*\*に存在します。

---

## ✅ 結論

**`i` が葉ノードのとき、`max-heapify(A, i)` は何もしないで終了する。**

---

## 🔍 理由

* 葉ノードには **子ノードが存在しない**ため、比較対象がいない。
* 擬似コード上でも `LEFT(i)` や `RIGHT(i)` が `heap-size` より大きくなり、`if` 条件がスキップされる。
* よって **swap も再帰も発生しない**。

---

## 🕒 実行時間

* **Θ(1)**（定数時間）
* 再帰呼び出しもなく、1回の比較だけで終了する最速パターン

---

## ✅ まとめ表

| 条件                    | 結果                       |
| --------------------- | ------------------------ |
| `i > ⌊heap-size / 2⌋` | ノード `i` は葉               |
|                       | `max-heapify(A, i)` は即終了 |
|                       | 木構造や配列には何も影響を与えない        |
| 実行時間                  | Θ(1)（非常に軽い）              |

---

## 5.max-heapifyのコードは再起呼び出しを除けば極めて小さい定数係数を持つ。しかしあるコンパイラは再起呼び出しを効率の悪いコードに変換するかもしれない。再帰呼び出しの代わりにループを用いる効率のいいmax-heapifyのコードをかけ。

以下に、**再帰を用いずループで書き換えた `MAX-HEAPIFY` の非再帰版擬似コード**を示します。

これは、\*\*末尾再帰（tail recursion）\*\*である `MAX-HEAPIFY` を、**ループ構造で書き直したもの**です。

---

## ✅ ループ版 `MAX-HEAPIFY(A, i)`

```plaintext
MAX-HEAPIFY(A, i)
    while true
        l ← LEFT(i)
        r ← RIGHT(i)
        largest ← i

        if l ≤ heap-size[A] and A[l] > A[largest]
            largest ← l
        if r ≤ heap-size[A] and A[r] > A[largest]
            largest ← r

        if largest = i
            break  // ヒープ条件を満たしているので終了

        swap A[i] ↔ A[largest]
        i ← largest  // 続けて次の子ノードへ下る
```

---

## 🔁 動作のポイント

* `largest ≠ i` なら swap して `i ← largest` に更新し、次のループで再ヒープ化
* もし `largest == i` なら、その部分木はすでに max-heap → `break`

---

## 🧠 メリット（再帰 vs ループ）

| 特徴             | 再帰版           | ループ版         |
| -------------- | ------------- | ------------ |
| 記述の簡潔さ         | ○（シンプル）       | △（やや長い）      |
| 関数呼び出しのオーバーヘッド | ✕（スタックが積まれる）  | ○（ループ内で処理）   |
| 実行時のパフォーマンス    | △（最適化されれば良い）  | ◎（確実に安定して速い） |
| コンパイラ依存        | 高い（最適化有無で影響大） | 低い（常に一定の効率）  |

---
## ✅ 実用上の注意

* 再帰深さが `log n` 程度なら問題ないが、**リアルタイム処理や大規模ヒープ処理ではループ版が安定**
* 特に **Cやアセンブリに近い最適化が重要な場面**では、再帰よりループの方が望ましい
---

## 6. サイズnのヒープ上のmax-heapifyの最悪実行時間がΩ(logn)であることを示せ。

`max-heapify` の**最悪実行時間が Ω(log n)** であることを示すには、
「最悪のケースで `max-heapify` が再帰的に**ヒープの高さ h = Θ(log n)** 回呼び出される」ことを示せば十分です。

---

## ✅ 観点：ヒープの性質

* ヒープは**完全二分木**なので、**高さ h = ⌊log₂ n⌋ = Θ(log n)**
* `max-heapify(A, i)` は、**ノード i の値が子より小さい限り再帰的に下へ進む**

---

## 🔍 最悪ケースの例

たとえば、次のような構造を考える：

```
        1        ← A[i] = 1 （親）
       / \
      10  9      ← 子（親より大）
     / \
    8   7
   ...
```

* ここで `max-heapify(A, 1)` を呼び出すと、**毎回最大の子と交換しながら最下層まで下りる**
* つまり、**ヒープの高さ h 回**の swap と比較が起きる

---

## 🔁 手続きの挙動

1. A\[1] = 1, 子 = 10 → swap → 次はA\[2]（値10）に対して再帰
2. A\[2] = 1, 子 = 8 → swap → 次はA\[4]（値8）に対して再帰
3. …
4. **最下層まで下りる**

---

## ✅ 証明：最悪時間は Ω(log n)

* 各段階で1回の swap と比較をする
* **再帰深さ = ヒープの高さ = Θ(log n)**
* よって、**最悪実行時間は Ω(log n)**

---

## ✅ 結論

> サイズ n のヒープに対して、max-heapify の最悪実行時間は **Ω(log n)**
> なぜなら、要素がルートから最下層まで下がる場合、\*\*ヒープの高さ分の再帰（またはループ）\*\*が必要だから

---