1. Ilustre a operacao heapify(3) no array [27,17,3,16,13,10,1,5,7,12,4,8,9,0].

Passo 1

O enunciado dá um array
[27,\,17,\,3,\,16,\,13,\,10,\,1,\,5,\,7,\,12,\,4,\,8,\,9,\,0]
e pede para ilustrar a chamada de \text{heapify}(3) supondo que usamos índice base 1 e a propriedade de max-heap. Vamos aplicar recursivamente o procedimento que compara o nó em i com seus filhos em 2i e 2i+1, trocando com o maior se necessário.

Passo 2

Começamos em i=3. O valor em \,A[3]=3. Seus filhos estão em
2\cdot3=6,\quad2\cdot3+1=7,
com valores
A[6]=10,\quad A[7]=1.
Entre \,3,\,10 e 1, o maior é 10 em A[6]. Logo, vamos trocar A[3] com A[6].

Passo 3

Após trocar A[3] com A[6], o array fica
[27,\,17,\,10,\,16,\,13,\,3,\,1,\,5,\,7,\,12,\,4,\,8,\,9,\,0].
Agora precisamos chamar \text{heapify} recursivamente em i=6.

Passo 4

Em i=6 temos A[6]=3. Seus filhos são
2\cdot6=12,\quad2\cdot6+1=13,
com valores
A[12]=8,\quad A[13]=9.
O maior entre 3,\,8,\,9 é 9 em A[13]. Trocamos A[6] com A[13], obtendo
[27,\,17,\,10,\,16,\,13,\,9,\,1,\,5,\,7,\,12,\,4,\,8,\,3,\,0].
Em seguida, chamamos \text{heapify} em i=13.

Passo 5

No índice i=13, o nó A[13]=3 não tem filhos ( 2\cdot13=26 passa do tamanho do array), logo a recursão para.

Resposta

O array final, após \text{heapify}(3), é
[27,\,17,\,10,\,16,\,13,\,9,\,1,\,5,\,7,\,12,\,4,\,8,\,3,\,0].

Exercícios relacionados