Considere um conjunto de 5 elementos. Usando o algoritmo HeapSort para ordenar em ordem decrescente, responda às seguintes perguntas:
Como ficará o vetor int numeros[] = {25,18,30,35,50} após e execução da função buildHeap(numeros, 5). Mostre passo a passo.
Como ficará o vetor int numeros[] = {25,18,30,35,50} após e execução da função buildHeap(numeros, 5). Mostre passo a passo.
Passo 1
Beleza, vamos lá! Você tem um conjunto de 5 números: {25, 18, 30, 35, 50} e quer ordenar esses números em ordem decrescente usando o algoritmo HeapSort. Hoje, vamos focar na parte inicial desse algoritmo, que é a função
buildHeap
. Para isso, precisamos entender como transformar nosso vetor numa estrutura de heap (mais especificamente, um max heap), onde cada pai é maior que seus filhos. Isso vai ajudar a organizar os números de forma que a maior deles fique no topo, facilitando a ordenação.Passo 2
Primeiro, vamos visualizar nosso vetor como se fosse uma árvore binária completa. Isso significa que cada nível da árvore está completamente preenchido, exceto possivelmente pelo último nível, que é preenchido da esquerda para a direita.
Nosso vetor inicial é:
Índices: 0 1 2 3 4
Valores: 25, 18, 30, 35, 50
Representando como árvore:
25
/ \
18 30
/ \
35 50
Passo 3
A função
buildHeap
começa a organizar o vetor em um heap a partir dos nós que têm filhos, ou seja, os nós internos. No nosso caso, os nós com índices 1 e 0, já que os índices 3 e 4 são folhas (não têm filhos).Vamos começar pelo último nó interno, que é o índice 1 (valor 18).
Passo 4
No índice 1, o valor é 18. Seus filhos estão nos índices:
- Filho esquerdo: 2 * i + 1 = 3 (valor 35)
- Filho direito: 2 * i + 2 = 4 (valor 50)
Agora, comparamos 18 com seus filhos 35 e 50. O maior valor entre eles é 50.
Passo 5
Como 50 (filho direito) é maior que 18 (pai), fazemos a troca:
Antes: [25, 18, 30, 35, 50]
Depois: [25, 50, 30, 35, 18]
Agora, precisamos verificar se a troca afetou a propriedade do heap no sub-árvore que foi modificada. Olhando para o novo valor no índice 4 (18), que é uma folha, não há mais nada para fazer aqui.
Passo 6
Agora, vamos para o próximo nó interno, que é o índice 0 (valor 25).
Seus filhos estão nos índices:
- Filho esquerdo: 1 (valor 50)
- Filho direito: 2 (valor 30)
Comparando 25 com 50 e 30, vemos que 50 é o maior.
Passo 7
Como 50 (filho esquerdo) é maior que 25 (pai), trocamos:
Antes: [25, 50, 30, 35, 18]
Depois: [50, 25, 30, 35, 18]
Agora, verificamos a sub-árvore afetada no índice 1 (valor 25).
Seus filhos:
- Filho esquerdo: 3 (valor 35)
- Filho direito: 4 (valor 18)
Comparando 25 com 35 e 18, 35 é o maior.
Passo 8
Como 35 (filho esquerdo) é maior que 25 (pai), trocamos novamente:
Antes: [50, 25, 30, 35, 18]
Depois: [50, 35, 30, 25, 18]
Agora, o valor no índice 3 (25) é uma folha, então terminamos a construção do heap.
Resposta
Após a execução da função
buildHeap(numeros, 5)
, o vetor fica assim:[50, 35, 30, 25, 18]