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.

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]

Exercícios relacionados