19906


n 個の要素を持つヒープの、高さ h における節点が n/2^(h+1) 個である、理由がわかりません。

問題文の原文はこちらです：

> Show that there are at most ⌈n/2^(h+1)⌉ nodes of height h in any n-element
> heap.

以下がIntroduction to Algorithms 練習問題6.3-3に対するInstructor's Manual
の解説ですが、なぜh=0が正しいからの証明から始まるのか、また＃は何をさしているのかよくわかりません。

もしもっとわかりやすい証明があれば、解説をお願いします。

[![解説1](https://i.stack.imgur.com/xUiYq.png)](https://i.stack.imgur.com/xUiYq.png)

[![解説2](https://i.stack.imgur.com/HFepL.png)](https://i.stack.imgur.com/HFepL.png)


CC BY-SA 3.0
2015-12-11T07:40:27.453
19871
2015-12-14T03:40:37.943
2015-12-14T03:40:37.943
13580
13580
question
アルゴリズム データ構造 ヒープ
ヒープデータ構造について


回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。

この問題は[二分ヒープ](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83%97)を対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8...となりますが、最後の段は2の累乗になっているとは限りません。また"at
most"はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。

ある関数f(k)があったとして、k=0,1,2,3...とします。f(k+1)をf(k)で表すことができるとき、初期条件f(0)が決まれば、あとは再帰的に答えが正しいことが証明できます。それがh=0の証明から始める理由です。これを[数学的帰納法(mathematical
induction)](https://ja.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E7%9A%84%E5%B8%B0%E7%B4%8D%E6%B3%95)と言います。

**説明中に出てくる変数**

n: ツリー中の全ノード数  
h: height（高さ）はノードを下から辿った数  
d: depthまたはlevel（深さ）はノードをルートから辿った数  
H: ツリー全体の高さ  
x: 最深部のノードの数

**base caseのnが偶数xが奇数の説明**  
絵を描いてみました。下手くそですみません。  
[![画像の説明をここに入力](https://i.stack.imgur.com/jcQgw.png)](https://i.stack.imgur.com/jcQgw.png)

**他の証明方法?**

xを末端の葉の数とした時、nは次のように表せますし、高さは最低log(n+1)あることを手掛かりに展開するような方向でいけるかもしれません。

[![全ノードの定義](https://i.stack.imgur.com/bdjjK.png)](https://i.stack.imgur.com/bdjjK.png)


CC BY-SA 3.0
2015-12-12T07:01:06.953
19906
2015-12-12T09:45:31.950
2015-12-12T09:45:31.950
7837
7837
19871
answer


> なぜh=0が正しいからの証明から始まるのか

英語も数学も苦手なので途中は一切見ていないのですが、最後の式をみる限り[数学的帰納法](https://ja.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E7%9A%84%E5%B8%B0%E7%B4%8D%E6%B3%95)で証明しているからでしょう。  
違和感があるのならh=1から始めても良いかと(h=0と比べると面倒になるのではないかと思いますが)。

> また＃は何をさしているのか

コメントで別の方が書かれている通りだと思います。

> もしもっとわかりやすい証明があれば、解説をお願いします。

<http://clrs.skanev.com/06/03/03.html> でどうでしょう。(最後は≦の誤記ですかね)

* * *

少なくとも出典は明記すべきですね。一般的にinstructor's
manualで分かるものなのでしょうか…？(私は分かりませんでした。検索してみるとたしかにそう呼ばれているそうですがいきなり書かれても固有名詞であることに気づけません…)

[Introduction to Algorithms](https://mitpress.mit.edu/books/introduction-
algorithms) 中のExercise 6.3-3に対する[Instructor's
Manual(※Amazonリンクです)](http://www.amazon.co.jp/dp/1495319288)に書かれている証明、ってことですよね？


CC BY-SA 3.0
2015-12-12T07:29:53.550
19907
2015-12-12T07:37:52.680
2015-12-12T07:37:52.680
2808
2808
19871
answer


他の回答者さんがおっしゃってるように、数学的帰納法を使っています。

文章の流れとしては（付番は本文のものとは無関係です)

  1. basis = 高さ0の場合の証明

    * 高さ0のノードの個数<=葉の数より、葉の数<=ceil(n/2)を証明すれば十分
    * 葉の数=ceil(n/2)の証明 （これが原文の大部分を占めています）
  2. inductive step = 高さh-1での成立を仮定して、高さhの場合の証明

というふうになっています。


CC BY-SA 3.0
2015-12-12T08:03:59.757
19908
2015-12-12T10:01:23.510
2015-12-12T10:01:23.510
13199
13199
19871
answer