Considere um conjunto de 5 elementos. Usando o algoritmo HeapSort para ordenar em ordem decrescente, responda às seguintes perguntas:
Qual é o número de movimentos necessários para ordenar os 5 elementos no pior dos casos? Justifique.

Passo 1

Beleza, vamos lá! O exercício pede para a gente analisar o algoritmo HeapSort aplicado a um conjunto de 5 elementos, ordenando-os em ordem decrescente. Nosso foco aqui é descobrir quantos movimentos (tipo, trocas de posição dos elementos) são necessários no pior cenário para realizar essa ordenação. Para resolver isso, vamos precisar entender como o HeapSort funciona e contar cada movimento que ele faz durante o processo.

Passo 2

Primeiro, vamos falar um pouco sobre o HeapSort. O HeapSort é um algoritmo de ordenação que utiliza uma estrutura de dados chamada heap, que é basicamente uma árvore binária completa onde cada pai é maior (ou menor, dependendo da ordenação) que seus filhos. No nosso caso, queremos ordenar em ordem decrescente, então vamos construir um heap máximo, onde o maior elemento está no topo.

Passo 3

O HeapSort funciona em duas etapas principais:
  1. Construção do heap máximo: Transformar o conjunto de elementos em um heap máximo.
  2. Ordenação: Repetidamente, retirar o maior elemento (que está no topo do heap) e colocá-lo na posição correta no array.
Vamos seguir essas etapas com os 5 elementos.

Passo 4

Construção do Heap Máximo:
Para construir o heap máximo, começamos a ajustar os elementos a partir do meio do array, movendo para baixo para garantir que cada subárvore satisfaz a propriedade do heap.
  • Suponha que temos os elementos: [A, B, C, D, E]
  • Vamos indexar de 0 a 4 para facilitar.
Primeiro, começamos pelo último nó não-folha, que no caso de 5 elementos é o índice 1.
  • Verificamos se os filhos de B (índices 3 e 4) são maiores que B.
  • Se sim, fazemos uma troca.
Cada troca conta como um movimento. Vamos supor que precisamos fazer uma troca aqui.
Depois, passamos para o índice 0 (A) e repetimos o processo.
Movimentos na Construção do Heap:
  • Supondo que fizemos 2 trocas durante essa fase.

Passo 5

Ordenação:
Agora que temos o heap máximo, começamos a ordenar:
  1. Troca o primeiro elemento (o maior, A) com o último elemento do heap (E).
  2. Reduz o tamanho do heap em 1 (não considera mais E).
  3. Reajusta o heap para garantir que ainda é um heap máximo.
  4. Repete o processo até que todo o array esteja ordenado.
Cada troca e cada ajuste do heap contam como movimentos.
Para 5 elementos:
  • Troca A e E: 1 movimento
  • Ajuste do heap: suponha 2 movimentos
  • Troca A e D: 1 movimento
  • Ajuste do heap: 2 movimentos
  • Troca A e C: 1 movimento
  • Ajuste do heap: 1 movimento
  • Troca A e B: 1 movimento
  • Ajuste final: 0 movimentos
Total de Movimentos na Ordenação:
  • 1 + 2 + 1 + 2 + 1 + 1 = 8 movimentos

Resposta

No pior dos casos, o HeapSort realiza 10 movimentos para ordenar os 5 elementos em ordem decrescente.

Exercícios relacionados