高さHのヒープ内の要素の最小および最大数は何ですか?
-
29-09-2020 - |
質問
私は質問を越えて来ました:
私がこの理論を思いついた高さのヒープの最小値と最大数は何ですか $ H $ ?
: $$ \ sum_ {i= 0} ^ {H-1} 2 ^ i= 2 ^ h-1 $$
$ 2 ^ h-1 $ は内部ノードであり、理解された事実によると理解されています。しかし、CLRS以外の場合は、完全なバイナリツリーとして言及されている
を介してほぼ完全なバイナリツリーであることがわかります。最大要素数を簡単に計算できます。 $$ \ sum_ {i= 0} ^ {h} 2 ^ i= 2 ^ {h + 1} -1 $$
しかし、最小要素数を計算するという点を取得することはできません。 それが次のようになるべきです。 $$ 2 ^ {h} + 1 $$ for $ 0 $ または $ 2 $ 子供のプロパティ
またはそれが次のようにしてください。 $$ 2 ^ {h} $$ for $ 0 $ または $ 1 $ 子供のプロパティ
リファレンス1:
リファレンス2: Heapsort
ありがとうございました。
解決
高さのヒープ $ h $ は、深さ $ H-1 $ レベル $ h $ に少なくとも1つのノードを持つ必要があります。
そのため、ノードの最小総数は少なくともなければなりません $ \ sum_ {i= 0} ^ {h - 1} 2 ^ i + 1= 2 ^ {h} -1 + 1= 2 ^ h。 $ 2 ^ h $ ノードのヒープ以降、$ とこのタイトは高さ $ H $ 。
所属していません cs.stackexchange