Questão - Heap binário

[Osvaldo Andrade]

Pessoal,

Alguém aí sabe a resposta dessa questão?

- Prove que em um heap binário, o número de elementos de uma subárvore é no máximo 2n/3.

[]'s

[Jhonatan Raphael]

Osvaldo,

Nem fiz essa e nem sei como começar, rs.. já tentou usar a prova do número máximo de elementos de um heap?

--

Att.

Jhonatan Ríchard Raphael

Bacharel em Ciência da Computação - UEMS
Mestrando em Ciência da Computação - UNICAMP

[Osvaldo Andrade]

Oi Johnatan, 

Consegui resolver da forma que enviei no último e-mail, não tenho certeza se está certo.

Mudando de assunto, você chegou a fazer o 6.1-7 do Cormen? 

O máximo que consegui foi o seguinte:

Resposta 6.1-7:

Em heaps binários, as folhas são indexadas após as não-folhas, e em heaps completos, o número de nós da último nível é igual a soma de todos os outros menos 1. Portanto não faz sentido em dizer que o número de nós não-folhas seja maior que piso(n/2), pois neste caso, o último filho do último nó não folha, estaria além do limite da heap, pois n = 2*(piso(n/2)) + 1, que é maior que n. 

Sendo assim, o maior índice possível de um nó não folha é exatamente piso(n/2), e por isso os nós pais podem ser indexados a partir da fórmula piso(n/2) e portanto nunca serão folhas.

Concluímos então que as folhas são indexadas por piso(n/2) +1..n.

[]'s