Quels sont les nombres minimaux et maximaux d'éléments dans un tas de hauteur h?

Question

Je suis tombé sur la question suivante:

quels sont les nombres minimaux et maximaux d'éléments dans un tas de hauteur $ h $ ?

à qui je suis venu avec cette théorie: $$ \ sum_ {i= 0} ^ {h-1} 2 ^ i= 2 ^ h-1 $$

2 ^ h-1 $ est les nœuds internes et qui est compris en fonction du fait compris. Mais parce que nulle part, sauf CLRS mentionne les tas d'être un arbre binaire presque complet partout, il est mentionné comme un arbre binaire complet.

Le nombre maximum d'éléments peut être facilement calculé: $$ \ sum_ {i= 0} ^ {h} 2 ^ i= 2 ^ {h + 1} -1 $$

Mais je ne peux pas avoir le point de calculer le nombre minimum d'éléments: Devrait-ce être: $$ 2 ^ {h} +1 $$ for $ 0 $ ou $ 2 $ propriété enfants

ou devrait-il être: $$ 2 ^ {h} $$ pour $ $ 0 $ ou $ 1 $ Propriété des enfants

Référence1: https://walkcccc.github.io/clrs/ CHAP06 / 6.1 / # 61-1

Référence2: tasort

merci.

Answer 1

Un tas de hauteur $ h $ est terminé jusqu'au niveau à la profondeur $ H-1 $ et doit avoir au moins un nœud sur niveau $ h $ .

Par conséquent, le nombre total minimum de nœuds doit être au moins $ \ sum_ {i= 0} ^ ^ {h-1} 2 ^ i + 1= 2 ^ {h} -1 + 1= 2 ^ h. $ , et cela serré depuis un tas avec 2 ^ h $ nœuds a la hauteur $ h $ .