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.
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:
- Construção do heap máximo: Transformar o conjunto de elementos em um heap máximo.
- 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:
- Troca o primeiro elemento (o maior, A) com o último elemento do heap (E).
- Reduz o tamanho do heap em 1 (não considera mais E).
- Reajusta o heap para garantir que ainda é um heap máximo.
- 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.