O que são o mínimo e o número máximo de elementos em uma pilha de altura h?

Question

Me deparei com a pergunta:

O que são o mínimo e o número máximo de elementos em uma pilha de altura $h$?

Para que vim, até a esta teoria:$$\sum_{i=0}^{h-1} 2^i = 2^h-1$$

$2^h-1$ é a nós internos e que é compreendido de acordo com o entendido fato.Mas porque em nenhum lugar, exceto CLRS menciona pilhas para ser um Árvore Binária Quase Completa em toda parte ele é mencionado como uma Árvore Binária.

O número máximo de elementos pode ser facilmente calculado:$$\sum_{i=0}^{h} 2^i = 2^{h+1}-1$$

Mas eu não posso chegar ao ponto de calcular o número mínimo de elementos:Deve ser:$$2^{h}+1$$ para $0$ ou $2$ crianças propriedade

Ou deveria ser:$$2^{h}$$ para $0$ ou $1$ crianças propriedade

Reference1: https://walkccc.github.io/CLRS/Chap06/6.1/#61-1

Reference2: HeapSort

Obrigado.

Answer 1

Um pilha de altura $h$ é completa até o nível de profundidade $h-1$ e tem de ter pelo menos um nó no nível $h$.

Portanto, o mínimo número total de nós deve ser, no mínimo, $ \sum_{i=0}^{h-1} 2^i + 1 = 2^{h}-1 + 1= 2^h.$, e esta apertado desde uma pilha com $2^h$ nós tem altura $h$.