質問: 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) ![解説2](https://i.stack.imgur.com/HFepL.png)
回答: 他の回答者さんがおっしゃってるように、数学的帰納法を使っています。 文章の流れとしては(付番は本文のものとは無関係です) 1. basis = 高さ0の場合の証明 * 高さ0のノードの個数<=葉の数より、葉の数<=ceil(n/2)を証明すれば十分 * 葉の数=ceil(n/2)の証明 (これが原文の大部分を占めています) 2. inductive step = 高さh-1での成立を仮定して、高さhの場合の証明 というふうになっています。