• 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:
  1. Heap Máximo: O valor de cada nó é maior ou igual aos valores dos seus filhos. Ou seja, o maior elemento está na raiz.
  2. 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:
  1. Construção do Heap: Transformamos o vetor desordenado em um Heap Máximo. Isso garante que o maior elemento esteja na raiz.
  2. 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.
  3. 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.
  4. 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.

Exercícios relacionados