Was sind die minimale und maximale Anzahl von Elementen in einem Höchsthaufen H?

Question

Ich bin auf die Frage gestoßen:

Wie hoch sind die minimalen und maximalen Anzahl von Elementen in einem Höchsthaufen $ H $ ?

, auf das ich mit dieser Theorie aufkam: $$ \ SUM_ {i= 0} ^ {H-1} 2 ^ i= 2 ^ H-1 $$

$ 2 ^ H-1 $ ist die internen Knoten und das wird gemäß der verstandenen Tatsache verstanden. Da nirgends Nirgendwo nur Clrs-Haufen erwähnt, um ein fast kompletter Binärbaum zu sein überall, wird er als kompletter Binärbaum erwähnt.

Die maximale Anzahl von Elementen kann leicht berechnet werden: $$ \ SUM_ {i= 0} ^ {h} 2 ^ i= 2 ^ {H + 1} -1 $$

aber ich kann nicht den Punkt des Berechnens der minimalen Anzahl von Elementen erhalten: Sollte es sein: $$ 2 ^ {h} +1 $$ für $ 0 $ oder $ 2 $ Kinder-Eigentum

oder sollte es sein: $$ 2 ^ {h} $$ für $ 0 $ oder $ 1 $ Kindereigenschaft

referenz1: https://walkccc.github.io/clrs/ Chap06 / 6.1 / # 61-1

reference2: hepper

danke.

Answer 1

ein Haufen der Höhe $ H $ ist vollständig auf dem Niveau in der Tiefe $ H-1 $ und muss mindestens einen Knoten auf Ebene $ H $ haben.

Daher muss die minimale Gesamtzahl der Knoten mindestens sein $ \ sum_ {i= 0} ^ {h-1} 2 ^ i + 1= 2 ^ {h} -1 + 1= 2 ^ h. $ und dieses eng, da ein Heap mit $ 2 ^ H $ -Knoten Höhe $ H $ .