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:
  1. P: Como o heap está vazio, ‘P’ é o primeiro elemento.
    [P]
    
  2. R: ‘R’ é maior que ‘P’, então ‘R’ sobe para a raiz.
    [R, P]
    
  3. O: ‘O’ é menor que ‘R’, fica como filho.
        R
       / \
      P   O
    
  4. G: ‘G’ é menor que ‘R’, fica como filho de ‘P’.
        R
       / \
      P   O
     /
    G
    
  5. R: Outro ‘R’ igual à raiz, pode ficar como filho de ‘O’.
        R
       / \
      P   O
     / \
    G   R
    
  6. A: ‘A’ é menor que ‘P’, fica como filho de ‘G’.
        R
       / \
      P   O
     / \
    G   R
    
/
A

7. **M**: 'M' é menor que 'R' mas maior que 'P', sobe para substituir 'P'.
   R
  / \
 M   O
/ \
G R
/
A

8. **A**: Outro 'A' fica como filho de 'R' à direita.
   R
  / \
 M   O
/ \   \
G R A
/
A

9. **R**: Mais um 'R' igual ao raiz, fica como filho de 'G'.
   R
  / \
 M   O
/ \   \
G R A
/
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:
  1. Troca o elemento da raiz (o maior) com o último elemento do heap.
  2. Remove o último elemento (que agora é o maior) da árvore.
  3. Reajusta o heap para manter a propriedade de Max-Heap.
  4. Repete o processo até que o heap esteja vazio.
Vamos aplicar passo a passo:
  1. Inicialmente:
    Heap: [R, M, O, G, R, A, A, R]
    Ordenado: []
    
  2. Primeira troca: Troca ‘R’ com ‘R’ (não muda).
    Heap: [R, M, O, G, R, A, A]
    Ordenado: [R]
    
  3. Segunda troca: Troca ‘R’ com ‘A’.
    Heap: [A, M, O, G, R, R]
    Ordenado: [R, A]
    
    Reajusta o heap:
        O
       / \
      M   R
     / \
    G   R
    
  4. Terceira troca: Troca ‘O’ com ‘R’.
    Heap: [R, M, A, G, R]
    Ordenado: [R, A, O]
    
    Reajusta o heap:
        R
       / \
      M   A
     / \
    G   R
    
  5. 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
    
  6. Quinta troca: Troca ‘R’ com ‘G’.
    Heap: [G, M, A]
    Ordenado: [R, A, O, R, G]
    
    Reajusta o heap:
        M
       / \
      G   A
    
  7. Sexta troca: Troca ‘M’ com ‘A’.
    Heap: [A, G]
    Ordenado: [R, A, O, R, G, M]
    
    Reajusta o heap:
        G
       /
      A
    
  8. Sétima troca: Troca ‘G’ com ‘A’.
    Heap: [A]
    Ordenado: [R, A, O, R, G, M, G]
    
  9. 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

Exercícios relacionados