Mostre o vetor resultante da inserção dos caracteres da palavra PROGRAMAR (nessa ordem) em um Max-Heap inicialmente vazio. Descreva o processo de construção do Heap e depois demonstre a execução do HeapSort para ordenar os caracteres em ordem alfabética.
Passo 1
Beleza, vamos resolver um exercício sobre Max-Heap e HeapSort usando a palavra “PROGRAMAR”. O que a gente vai precisar entender é como construir um Max-Heap inserindo os caracteres um a um e depois como aplicar o HeapSort para ordenar esses caracteres em ordem alfabética. Vamos por partes para facilitar!
Passo 2
Primeiro, vamos entender o que é um Max-Heap. É uma estrutura de dados em forma de árvore binária onde cada pai é maior ou igual aos seus filhos. No nosso caso, vamos considerar a ordem alfabética, onde ‘Z’ é maior que ‘A’. Começamos com um heap vazio e vamos inserindo os caracteres da palavra “PROGRAMAR” na ordem que aparecem.
Passo 3
Vamos inserir os caracteres um a um no heap:
-
P: Como o heap está vazio, ‘P’ é o primeiro elemento.
[P]
-
R: ‘R’ é maior que ‘P’, então ‘R’ sobe para a raiz.
[R, P]
-
O: ‘O’ é menor que ‘R’, fica como filho.
R / \ P O
-
G: ‘G’ é menor que ‘R’, fica como filho de ‘P’.
R / \ P O / G
-
R: Outro ‘R’ igual à raiz, pode ficar como filho de ‘O’.
R / \ P O / \ G R
-
A: ‘A’ é menor que ‘P’, fica como filho de ‘G’.
R / \ P O / \ G R
/
A
A
7. **M**: 'M' é menor que 'R' mas maior que 'P', sobe para substituir 'P'.
R
/ \
M O
/ \
G R
/
A
/
A
8. **A**: Outro 'A' fica como filho de 'R' à direita.
R
/ \
M O
/ \ \
G R A
/
A
/
A
9. **R**: Mais um 'R' igual ao raiz, fica como filho de 'G'.
R
/ \
M O
/ \ \
G R A
/
A R
/
A R
Passo 4
Agora que construímos o Max-Heap, vamos aplicar o HeapSort para ordenar os caracteres em ordem alfabética. O HeapSort funciona assim:
- Troca o elemento da raiz (o maior) com o último elemento do heap.
- Remove o último elemento (que agora é o maior) da árvore.
- Reajusta o heap para manter a propriedade de Max-Heap.
- Repete o processo até que o heap esteja vazio.
Vamos aplicar passo a passo:
-
Inicialmente:
Heap: [R, M, O, G, R, A, A, R] Ordenado: []
-
Primeira troca: Troca ‘R’ com ‘R’ (não muda).
Heap: [R, M, O, G, R, A, A] Ordenado: [R]
-
Segunda troca: Troca ‘R’ com ‘A’.
Heap: [A, M, O, G, R, R] Ordenado: [R, A]
Reajusta o heap:O / \ M R / \ G R
-
Terceira troca: Troca ‘O’ com ‘R’.
Heap: [R, M, A, G, R] Ordenado: [R, A, O]
Reajusta o heap:R / \ M A / \ G R
-
Quarta troca: Troca ‘R’ com ‘R’ (não muda).
Heap: [R, M, A, G] Ordenado: [R, A, O, R]
Reajusta o heap:R / \ M A / G
-
Quinta troca: Troca ‘R’ com ‘G’.
Heap: [G, M, A] Ordenado: [R, A, O, R, G]
Reajusta o heap:M / \ G A
-
Sexta troca: Troca ‘M’ com ‘A’.
Heap: [A, G] Ordenado: [R, A, O, R, G, M]
Reajusta o heap:G / A
-
Sétima troca: Troca ‘G’ com ‘A’.
Heap: [A] Ordenado: [R, A, O, R, G, M, G]
-
Oitava troca: Troca ‘A’ (último elemento).
Heap: [] Ordenado: [R, A, O, R, G, M, G, A]
Resposta
Após aplicar o HeapSort, os caracteres da palavra “PROGRAMAR” ordenados em ordem alfabética ficam assim:
A, A, G, G, M, O, R, R, R