Quali sono i numeri minimi e massimi di elementi in un mucchio di altezza h?

Question

Mi sono imbattuto nella domanda:

.

Quali sono i numeri minimi e massimi di elementi in un mucchio di altezza $ h $ ?

A cui ho inventato questa teoria: $$ \ sum_ {i= 0} ^ {h-1} 2 ^ i= 2 ^ h-1 $$

$ 2 ^ h-1 $ I nodi interni e che sono intesi secondo il fatto inteso. Ma perché da nessuna parte tranne CLRS menziona i cumulizzi per essere un quasi completo albero binario ovunque è menzionato come albero binario completo.

Il numero massimo di elementi può essere facilmente calcolato: $$ \ sum_ {i= 0} ^ {h} 2 ^ i= 2 ^ {h + 1} -1 $$

Ma non riesco a ottenere il punto di elaborare il numero minimo di elementi: Dovrebbe essere: $$ 2 ^ {h} +1 $$ per $ 0 $ o $ 2 $ Proprietà per bambini

o dovrebbe essere: $$ 2 ^ {h} $$ per $ 0 $ o $ 1 $ Proprietà per bambini

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

Riferimento2: heapsort

Grazie.

Answer 1

Un mucchio di altezza $ h $ è completato fino al livello a profondità $ h-1 $ e ha bisogno di avere almeno un nodo su livello $ h $ .

Pertanto il numero minimo del numero totale di nodi deve essere almeno $ \ sum_ {i= 0} ^ {h-1} 2 ^ i + 1= 2 ^ {h} -1 + 1= 2 ^ h. $ , e questo stretto poiché un mucchio con $ 2 ^ h $ nodi ha altezza $ h $ .