第3版　[解答]アルゴリズムイントロダクション 6-1:ヒープ

# 第3版 アルゴリズムイントロダクション 6-1:ヒープ練習問題の解答です。

## 問題1.高さhのヒープが持つ要素数の最大値と最小値を求めよ

ヒープ（完全二分木）を高さ *h* としたとき、

1. **各レベルのノード数**
   レベル 0 （根）には 1 個、レベル 1 には 2 個、…、レベル *k* には 2^k 個のノードがあります。

2. **最大要素数**
   最下層（レベル *h*）まで完全に埋まっている場合、レベル 0 から *h* までのノード数の総和なので、

   ```
   1 + 2 + 2^2 + … + 2^h = 2^{h+1} − 1
   ```

   つまり **最大要素数 = 2^{h+1} − 1**。

3. **最小要素数**
   高さ *h* を維持するには、最下層に最低でも 1 個はノードが必要です。一方、レベル 0～(h−1) までは完全に埋まっていると最少となるため、

   ```
   (1 + 2 + … + 2^{h−1}) + 1 = (2^h − 1) + 1 = 2^h
   ```

   つまり **最小要素数 = 2^h**。

---

**まとめ**

* 最小要素数： 2^h
* 最大要素数： 2^{h+1} − 1

## 2. 要素数がnのヒープの高さが下限がlognとなることを示せ。
高さ $h$ のヒープに要素が $n$ 個あるとき、その高さ $h$ は最低でも $\log_2 n$ に比例する（すなわち $\Omega(\log n)$）ことを示します。

---

### 1. ヒープ（完全二分木）の要素数の上界より

前問で示したように、高さ $h$ の完全二分木（ヒープ）の**最大**要素数は

$$
n_{\max} = 2^{h+1} - 1
$$

でした。

ヒープに実際に含まれる要素数を $n$ とすると、

$$
n \le 2^{h+1} - 1
$$

が成り立ちます。

---

### 2. 不等式を対数で解く

$$
n \le 2^{h+1} - 1
$$

に $+1$ をして、

$$
n + 1 \le 2^{h+1}
$$

両辺を $\log_2$ で取り、

$$
\log_2(n + 1) \le h + 1
$$

したがって

$$
h \ge \log_2(n + 1) - 1
$$

となります。

---

### 3. 結論

* 定数や切り捨てを無視すると、

  $$
  h = \Omega(\log_2 n)
  $$
* より厳密には

  $$
  h \ge \lfloor \log_2 n\rfloor
  $$

  （または $\lceil\log_2(n+1)\rceil - 1$）が成り立ちます。

したがって、「要素数 $n$ のヒープの高さは下限として $\log_2 n$ 以上である」ことが示されました。

## 3.maxヒープの部分木が含む最大要素はその部分木の根にあることを示せ。
3. **証明（帰納法による）**

部分木を根 $r$ とし，高さ（深さ）を $h$ とします。部分木全体の要素数を問わず，根の要素が最大であることを示します。

---

#### (1) 帰納基底（高さ $h=0$ のとき）

* 部分木がただひとつのノード（葉）のみ，つまり高さ 0 の場合は，自明にそのノード自身が最大で，かつ根です。

---

#### (2) 帰納ステップ（高さ $h$ の場合を仮定し，高さ $h+1$ の場合を考える）

1. **帰納法の仮定**
   高さ $h$ 以下の任意の部分木について，「その部分木に含まれる最大要素は根にある」ことが成り立つと仮定する。

2. **高さ $h+1$ の部分木**
   部分木の根を $r$，その左右の子への部分木をそれぞれ根 $c_1$，$c_2$ とします。

3. **ヒープ性（Max-Heap Property）**
   Max-Heap では常に

   $$
     A[r] \;\ge\; A[c_1],\quad
     A[r] \;\ge\; A[c_2]
   $$

   が成り立ちます。

4. **帰納法の適用**
   高さ $h+1$ の部分木の「子部分木」はいずれも高さ $h$ 以下です。
   仮定より、子部分木それぞれの最大要素はその根 $c_1$, $c_2$ にあります。
   したがって，部分木全体に含まれるすべての要素は

   $$
     A[r],\quad
     (\text{子部分木のすべての要素} \le A[c_1]),\quad
     (\text{子部分木のすべての要素} \le A[c_2])
   $$

   のいずれかです。

5. **結論**
   ヒープ性により $A[r]$ は $A[c_1]$ および $A[c_2]$ 以上なので，部分木のどの要素よりも大きい。
   したがって高さ $h+1$ の部分木でも「最大要素は根にある」ことが示されました。

---

以上により、任意の高さの部分木について，その部分木に含まれる最大要素は必ずその根ノードにあることが証明されました。

## 4.全ての要素が異なるときmaxヒープないの最小要素が置かれる可能性のある場所はどこか？
最小要素は必ず「葉ノード」のいずれかに置かれます。

---

### 理由（反証法）

1. 仮に最小要素 $m$ が内部ノード（子を持つノード）にあるとします。
2. そのノードには少なくとも１つ子がいるので、Max-Heap 性より親ノードの値は子ノードの値以上です。
3. しかし子ノードの値はすべて親ノードより小さいため、もし親が最小要素なら子もそれより小さくなってしまい矛盾します。
4. よって最小要素は「子を持たないノード」でなければならず、これはすなわち葉ノードです。

---

### 葉ノードの位置（配列表現の場合）

ヒープを 1 インデックスの配列 $A[1\ldots n]$ で表すとき、葉ノードは添字 $i$ が

$$
\biggl\lfloor \frac{n}{2} \biggr\rfloor + 1 \;\le\; i \;\le\; n
$$

を満たす要素になります。

したがって、要素数 $n$ の Max-Heap で全要素が異なるとき、最小要素は上記の範囲内のいずれかの位置にのみ現れ得ます。

## 5.既ソート配列はminヒープか？

昇順（非減少順）に並んだ配列を、そのまま 1-indexed のヒープ表現とみなすと、常に min-heap の性質を満たします。理由は以下のとおりです。

1. **配列表現と子・親の関係**
   1-indexed 配列 $A[1\ldots n]$ において、添字 $i$ の要素の子はそれぞれ

   $$
     A[2i]\quad(\text{左子}),\qquad A[2i+1]\quad(\text{右子})
   $$

   となります（存在する場合）。

2. **昇順ソート済みゆえの単調性**
   $A$ が昇順ソート済み、すなわち

   $$
     A[1] \le A[2] \le \cdots \le A[n]
   $$

   となっているとき、任意の $i$ とその子インデックス $2i,2i+1$ （いずれも $>i$）について

   $$
     A[i] \le A[2i],\quad A[i] \le A[2i+1]
   $$

   が自明に成り立ちます。

3. **結論**
   したがって、昇順ソートされた配列はそのまま min-heap の条件（親ノードの値が常に子ノード以下）を満たす、**有効な min-heap** になります。

---

**補足**

* 逆に、降順ソート済み（大きい値が前）の配列をヒープとみなすと、min-heap どころか max-heap すら保証されません。
* 昇順ソート済み配列は「完全二分木としては一見ランダムに値が割り当てられている」わけではなく、単にヒープ条件を満たすだけなので、ヒープ構造を活かした最小値取り出し（`extract-min`）は常に $O(\log n)$ で動きますが、ソート済みという情報は特に利用されません。


## 6.数列(23, 17, 14, 6, 13, 10, 1, 5, 7, 12)はmaxヒープか？

いいえ、この配列は Max-Heap ではありません。配列表現 $A[1\ldots10]$ として、親子関係をチェックすると：

| インデックス $i$ | $A[i]$ | 左子 $A[2i]$ | 右子 $A[2i+1]$ | 比較                       |
| ---------- | ------ | ---------- | ------------ | ------------------------ |
| 1          | 23     | 17         | 14           | $23\ge17,23\ge14$ OK     |
| 2          | 17     | 6          | 13           | $17\ge6,17\ge13$ OK      |
| 3          | 14     | 10         | 1            | $14\ge10,14\ge1$ OK      |
| 4          | 6      | 5          | 7            | $6\ge5$ OK, **$6<7$** NG |
| 5          | 13     | 12         | —            | $13\ge12$ OK             |

インデックス4 のノード（値 6）について，右子ノード（インデックス9）の値 7 のほうが大きいため，Max-Heap の性質（親 ≥ 子）が破られています。
したがって、この数列は Max-Heap ではありません。

## 7.要素数がnのヒープが格納されている配列において、葉は添字が下限(n/2) + 1, 以降の節点であることを示せ。

配列 $A[1\ldots n]$ でヒープを表すとき、ノード $i$ の子ノードは添字 $2i$（左子）および $2i+1$（右子）に対応します。ここから以下のように示せます。

---

1. **内部ノードの条件**
   ノード $i$ が少なくとも左子を持つには

   $$
     2i \le n
   $$

   が必要です。つまり

   $$
     i \le \frac{n}{2}
   $$

   を満たす $i$ はすべて「子を持つ可能性がある＝内部ノード候補」です。添字は整数なので、内部ノードとなりうるのは

   $$
     1 \le i \le \bigl\lfloor \tfrac{n}{2}\bigr\rfloor
   $$

   です。

2. **葉ノードの条件**
   ノード $i$ が **子を一つも持たない** （＝葉）ためには、左子すら存在しない必要があります。すなわち

   $$
     2i > n
   $$

   を満たす $i$ が葉です。両辺を 2 で割って

   $$
     i > \frac{n}{2}
   $$

   となる整数 $i$ を取ると、

   $$
     \bigl\lfloor\tfrac{n}{2}\bigr\rfloor + 1 \;\le\; i \;\le\; n
   $$

   がちょうど葉ノードの添字範囲になります。

---

**結論**
要素数 $n$ のヒープを 1-indexed 配列表現したとき、葉ノードは添字

$$
\boxed{\lfloor n/2\rfloor + 1 \;\le\; i \;\le\; n}
$$

の位置に置かれることが示されました。