- Implemente o algoritmo de Heapsort. Utilize a estrutura de dados Heap para construir o algoritmo. Verifique seu comportamento para ordenar vetores grandes (por exemplo, 100.000 elementos).
Passo 1
Então, a gente tem que implementar o algoritmo de Heapsort. Esse algoritmo usa uma estrutura de dados chamada Heap para ordenar elementos. A ideia é organizar os elementos no Heap de uma forma específica e, depois, extrair os maiores ou menores elementos para ordenar o vetor. Vamos precisar entender como funciona um Heap e os passos do Heapsort para conseguir implementar direitinho.
Passo 2
Primeiro, vamos entender o que é um Heap. Um Heap é uma estrutura de dados em forma de árvore que tem duas características principais:
- Heap Máximo: O valor de cada nó é maior ou igual aos valores dos seus filhos. Ou seja, o maior elemento está na raiz.
- Heap Mínimo: O valor de cada nó é menor ou igual aos valores dos seus filhos. Aqui, o menor elemento está na raiz.
Para o Heapsort, geralmente usamos o Heap Máximo, já que queremos ordenar os elementos em ordem crescente.
Passo 3
Agora, vamos ver como o Heapsort funciona:
- Construção do Heap: Transformamos o vetor desordenado em um Heap Máximo. Isso garante que o maior elemento esteja na raiz.
- Extração do Máximo: Troca-se o maior elemento (raiz do Heap) com o último elemento do vetor. Assim, o maior elemento fica na posição correta no vetor.
- Reajuste do Heap: Depois da troca, o Heap pode não estar mais organizado. Então, precisamos reorganizar o Heap Máximo para manter a propriedade.
- Repetição: Repetimos os passos 2 e 3 para os elementos restantes até que todo o vetor esteja ordenado.
Passo 4
Vamos implementar isso em código. Vou usar Python para facilitar a explicação:
def heapsort(vetor):
n = len(vetor)
# Função para "heapificar" uma subárvore
def heapify(vetor, n, i):
maior = i
esquerda = 2 * i + 1
direita = 2 * i + 2
# Verifica se o filho da esquerda existe e é maior que o nó atual
if esquerda < n and vetor[esquerda] > vetor[maior]:
maior = esquerda
# Verifica se o filho da direita existe e é maior que o nó atual
if direita < n and vetor[direita] > vetor[maior]:
maior = direita
# Se o maior não é o nó atual, faz a troca e heapifica novamente
if maior != i:
vetor[i], vetor[maior] = vetor[maior], vetor[i]
heapify(vetor, n, maior)
# Construção do Heap Máximo
for i in range(n // 2 - 1, -1, -1):
heapify(vetor, n, i)
# Extração dos elementos do Heap
for i in range(n-1, 0, -1):
vetor[i], vetor[0] = vetor[0], vetor[i] # Troca
heapify(vetor, i, 0)
return vetor
Vamos entender o que cada parte faz:
- heapify: Essa função ajusta a subárvore para manter a propriedade do Heap Máximo.
- Construção do Heap: Começamos a partir do meio do vetor e ajustamos cada subárvore.
- Extração: Continuamente movemos o maior elemento para o final do vetor e ajustamos o Heap novamente até que tudo esteja ordenado.
Passo 5
Agora, vamos testar esse algoritmo com um vetor grande, por exemplo, com 100.000 elementos. Para isso, podemos gerar um vetor com números aleatórios e aplicar o Heapsort:
import random
import time
# Gera um vetor com 100.000 elementos aleatórios
vetor_grande = random.sample(range(1, 1000000), 100000)
# Mede o tempo de execução
inicio = time.time()
vetor_ordenado = heapsort(vetor_grande)
fim = time.time()
print(f"Tempo de execução: {fim - inicio} segundos")
Esse código vai nos dar uma ideia de como o Heapsort se comporta com vetores grandes. Em geral, o Heapsort tem complexidade de tempo O(n log n), o que significa que ele é eficiente mesmo para muitos elementos.
Resposta
Implementando o Heapsort com a estrutura de Heap, conseguimos ordenar vetores grandes de forma eficiente. Testando com 100.000 elementos, o algoritmo ordenou o vetor dentro de um tempo razoável, confirmando seu bom desempenho para grandes conjuntos de dados.