Provar que um heap binário possui

16

Eu estou tentando provar que um montão binária com n nodos tem exatamente n2folhas, 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 preenchidok+1k

  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?

varatis
fonte
@ DaveClarke: Não é bem assim; a questão vinculada é o resultado de um mal-entendido sobre as partes dos editores deixadas lá para referência.
Raphael
Você já tentou indução sobre o número do nó resp. número de inserções?
Raphael
@DaveClarke: Por quê? É uma pergunta válida em si mesma, imho.
Raphael
BTW, a questão não tem nada a ver com montões. A reivindicação é válida para qualquer árvore binária completa
Ran G.

Respostas:

8

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.kk1

Então a prova é assim.

  1. Uma árvore perfeita de profundidade tem exatamente 2 k + 1 - 1 nós.k2k+11
  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á)k12k1
    2. no último nível, existem exatamente nós, que são todos folhas.n2k+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 + 12k1k1são pais e o resto2k-1-n-2 k +1n2k+12são folhas.2k1n2k+12
  5. A quantidade total de folhas é que lhe dá o que você precisa.
    n2k+1+2k1n2k+12
Tocou.
fonte
1
Observe que full é diferente de complete e diferente de árvores binárias perfeitas . Escolha infeliz, ambígua e inconsistente de palavras, mas o que você pode fazer sobre isso? Eu acho que seguir a definição da Wikipedia faz sentido, pois a maioria procurará lá primeiro?
Raphael
Uau, eu nem conhecia esses termos. Obrigado por apontar isso.
Ran G.
"até o nível k − 1, a árvore é perfeita (e possui 2 ^ k - 1 nós lá)" e "Assim, dos 2 ^ (k − 1) nós no nível k − 1" parecem declarações conflitantes, Ou eu estou esquecendo de alguma coisa?
Adriano h.
2k12k12k1+2k2+...
Ah, você está completamente certo, muito obrigado pelo esclarecimento!
Adriano h.
11

Aqui está uma prova lógica mais simples.

nthn/2n/2+1)thn/2

(n/2)(n/2)

Zubin Pahuja
fonte
1
Explicação bastante intuitiva e clara. Obrigado.
whitehat