O que são o mínimo e o número máximo de elementos em uma pilha de altura h?
-
29-09-2020 - |
Pergunta
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.
Solução
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$.