Provar que um heap binário possui

Eu estou tentando provar que um montão binária com $n$ nodos tem exatamente $\left\lceil \frac{n}{2} \right\rceil$folhas, dado que o heap é construído da seguinte maneira:

Cada novo nó é inserido via percolate up . Isso significa que cada novo nó deve ser criado no próximo filho disponível. O que quero dizer com isso é que as crianças são preenchidas de nível inferior e da esquerda para a direita. Por exemplo, o seguinte heap:

    0
   / \
  1   2

teria que ter sido construído nesta ordem: 0, 1, 2. (Os números são apenas índices, eles não dão nenhuma indicação dos dados reais mantidos nesse nó.)

Isso tem duas implicações importantes:

1. Não pode existir nó no nível sem o nível k estar completamente preenchido$k+1$$k$

2. Como os filhos são criados da esquerda para a direita, não pode haver "espaços vazios" entre os nós no nível ou situações como a seguinte: $k+1$

       0
      / \
     1   2
    / \   \
   3  4    6
   

(Isso seria um heap ilegal pela minha definição.) Assim, uma boa maneira de pensar nesse heap é uma implementação de array de um heap, onde não pode haver nenhum "salto" nos indeces do array.

Então, eu estava pensando que a indução provavelmente seria uma boa maneira de fazer isso ... Talvez algo que precise lidar com casos ímpares para n. Por exemplo, alguma indução usando o fato de que mesmo pilhas montadas dessa maneira devem ter um nó interno com um filho para um n par e nenhum nó para um n ímpar. Ideias?

Se eu receber sua pergunta corretamente, o heap obtido é apenas uma árvore binária ordenada, onde, em ordenado, quero dizer que o ésimo nível só pode ser ocupado após o nível k - 1 ter sido completamente preenchido, e cada nível é ocupado da esquerda para a direita, sem pular.$k$$k-1$

Então a prova é assim.

1. Uma árvore perfeita de profundidade tem exatamente 2 k + 1 - 1 nós.$k$$2^{k+1}-1$
2. Suponha que o heap atinja a profundidade . portanto $k$
   1. até o nível a árvore é perfeita (e tem 2 nós k - 1 lá)$k-1$$2^k-1$
   2. no último nível, existem exatamente nós, que são todos folhas.$n-2^k+1$
3. Cada folha no ésimo nível tem um pai. Além disso, cada duas folhas consecutivas têm o mesmo pai (talvez, exceto o último nó, cujo pai tenha apenas um filho)$k$
4. Assim, dos nós k - 1 no nível k - 1 , ⌈ n - 2 k + $2^{k-1}$$k-1$são pais e o resto2k-1-⌈n-2 k +$\left\lceil \frac{n-2^{k}+1}{2} \right\rceil$são folhas.$2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$
5. A quantidade total de folhas é que lhe dá o que você precisa. $$n-2^k+1 + 2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$$

Aqui está uma prova lógica mais simples.

$n^{th}$$\lfloor{n/2}\rfloor$$\lfloor n/2 +1\rfloor)^{th}$$\lfloor{n/2}\rfloor$

$\lfloor(n/2)\rfloor$$\lceil(n/2)\rceil$