Questão 26 Considere um heap H com 24 elementos tendo seu maior elemento na raiz. Em quantos nós de H pode estar o seu segundo menor elemento?

a) 18
b) 15
c) 14
d) 13
e) 12

Gabarito: d (Selecione o texto a esquerda para ver a resposta ou consulte o fim do post).

Explicação: Um Heap é uma estrutura de dados organizada como árvore binária (com algumas diferenças).

Sua inserção é sempre feita no nível mais distante (mais longe da raiz) e sempre da esquerda para a direita. Essa inserção não faz os elementos ficarem desordenados pois a cada inserção são feitas trocas, (mais detalhes e código da inserção e remoção em heap) caso seja necessário, e os elementos maiores (em heaps de máximo) nunca serão filhos de elementos menores.

Sabendo isso a questão se torna trivial. Veja a figura:

Esta é a única forma possível de um Heap com 24 elementos. Agora precisamos saber em quantas posições pode estar o segundo menor elemento deste heap.

Qual a condição para um nó possuir o segundo menor elemento?

Ele deve ser pai de no máximo 1 elemento. Caso ele seja pai de mais de 1 elemento ele já é maior que, no mínimo, 2 elementos! Sendo maior que, no mínimo, 2 elementos ele não poderá ser o segundo menor elemento.

Agora basta contarmos quantos nós são pais de 0 ou 1 nós.

Obteremos 13 nós (os circulados de vermelho na figura acima), que é a resposta correta!

Não concorda? 
Comente, opine e demonstre seu conhecimento!

Gabarito: d