Binary Heap e HeapSort – O que são e como funcionam

O que é Binary Heap?

Definição de Binary Heap

Um Binary Heap é uma estrutura de dados que representa uma árvore binária completa. Nesse tipo de árvore, todos os níveis, exceto possivelmente o último, estão completamente preenchidos, e todos os nós estão tão à esquerda quanto possível.

Max Heap e Min Heap

Existem duas variações de Binary Heap: Max Heap e Min Heap. No Max Heap, os pais têm valores maiores que ou iguais aos dos filhos, enquanto no Min Heap, os pais têm valores menores que ou iguais aos dos filhos.

Como funciona um Binary Heap

Propriedade de Heap

A principal característica que define um Binary Heap é a propriedade de heap. Cada nó da árvore deve respeitar essa propriedade em relação aos seus filhos, garantindo a ordenação dos elementos.

Operações em Binary Heap

As operações comuns em um Binary Heap incluem inserção, exclusão e busca. Essas operações garantem a manutenção da propriedade de heap.

O que é HeapSort?

Descrição do algoritmo HeapSort

HeapSort é um algoritmo de ordenação que usa um Binary Heap para classificar os elementos. Ele opera construindo o heap, extraindo repetidamente o elemento máximo (ou mínimo) e reconstituindo o heap.

Como o HeapSort funciona

Construindo o Heap

A primeira fase do HeapSort envolve a construção do heap a partir do conjunto de dados. Esta etapa prepara a estrutura para a extração dos elementos

Extraindo o Elemento Máximo ou Mínimo

Depois que o heap é construído, o HeapSort extrai repetidamente o elemento máximo (ou mínimo) da estrutura.

Reconstituição do Heap

Após a extração de um elemento, o HeapSort reconstitui o heap para manter a propriedade de heap. Este passo é repetido até que todos os elementos sejam extraídos e ordenados.

A eficiência do HeapSort

Complexidade de tempo do HeapSort

A beleza do HeapSort reside em sua eficiência. A complexidade de tempo do HeapSort é O(n log n), tornando-o eficiente para a ordenação de grandes conjuntos de dados.

Binary Heap e HeapSort na prática

Aplicações de Binary Heap e HeapSort

Os conceitos de Binary Heap e HeapSort não são apenas teoria. Eles são aplicados em muitas áreas, como sistemas de banco de dados, simulação de eventos discretos e algoritmos de caminho mais curto.

Exemplo de implementação em C#

C#
using System;

public class BinaryHeap
{
    private int[] heap;
    private int size;

    public BinaryHeap(int capacity)
    {
        heap = new int[capacity];
        size = 0;
    }

    private void Heapify(int index)
    {
        int largest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < size && heap[leftChild] > heap[largest])
            largest = leftChild;

        if (rightChild < size && heap[rightChild] > heap[largest])
            largest = rightChild;

        if (largest != index)
        {
            Swap(index, largest);
            Heapify(largest);
        }
    }

    private void Swap(int i, int j)
    {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public void Insert(int value)
    {
        if (size == heap.Length)
            throw new InvalidOperationException("Heap is full.");

        int currentIndex = size;
        heap[currentIndex] = value;
        size++;

        while (currentIndex > 0 && heap[currentIndex] > heap[(currentIndex - 1) / 2])
        {
            Swap(currentIndex, (currentIndex - 1) / 2);
            currentIndex = (currentIndex - 1) / 2;
        }
    }

    public int RemoveMax()
    {
        if (size == 0)
            throw new InvalidOperationException("Heap is empty.");

        int max = heap[0];
        heap[0] = heap[size - 1];
        size--;

        Heapify(0);

        return max;
    }

    public void HeapSort()
    {
        for (int i = size / 2 - 1; i >= 0; i--)
            Heapify(i);

        for (int i = size - 1; i >= 0; i--)
        {
            Swap(0, i);
            Heapify(0);
        }
    }
}

public class Program
{
    public static void Main()
    {
        int[] array = { 7, 3, 9, 2, 4, 1, 5 };

        BinaryHeap heap = new BinaryHeap(array.Length);

        foreach (int num in array)
            heap.Insert(num);

        Console.WriteLine("Original array:");
        foreach (int num in array)
            Console.Write(num + " ");

        heap.HeapSort();

        Console.WriteLine("\n\nSorted array:");
        while (heap.Size > 0)
        {
            int max = heap.RemoveMax();
            Console.Write(max + " ");
        }
    }
}

// Fonte: ChatGPT

O código apresentado implementa um Binary Heap e utiliza o algoritmo HeapSort para classificar um array de inteiros em ordem crescente. Vamos entender como funciona:

  • A classe BinaryHeap representa a estrutura do Binary Heap. Ela possui um array interno chamado heap que armazena os elementos e uma variável size que controla o número de elementos atualmente no heap.
  • O método Heapify é responsável por manter a propriedade de heap no Binary Heap. Ele compara o elemento atual com seus filhos e, se necessário, realiza trocas para garantir que o maior elemento esteja na posição correta.
  • O método Insert é usado para inserir um novo elemento no Binary Heap. Ele adiciona o elemento no final do array e realiza uma série de trocas para posicionar o elemento na posição correta de acordo com a propriedade de heap.
  • O método RemoveMax remove o elemento máximo (raiz) do Binary Heap e o substitui pelo último elemento do heap. Em seguida, ele chama o método Heapify para restaurar a propriedade de heap.
  • O método HeapSort utiliza o Binary Heap para ordenar o array. Primeiro, ele constrói o heap a partir dos elementos do array. Em seguida, repetidamente extrai o elemento máximo (raiz) do heap, realiza a troca com o último elemento não classificado e reconstitui o heap. Esse processo é repetido até que todos os elementos estejam classificados em ordem crescente.
  • No método Main, um array de inteiros é criado e inserido no Binary Heap. Em seguida, o algoritmo HeapSort é aplicado ao heap, resultando em um array ordenado. O array original e o array ordenado são exibidos no console.

Exemplo de implementação em Java

Java
import java.util.Arrays;

public class BinaryHeapHeapSortExample {
    private int[] heap;
    private int size;

    public BinaryHeapHeapSortExample(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    private void heapify(int index) {
        int largest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < size && heap[leftChild] > heap[largest])
            largest = leftChild;

        if (rightChild < size && heap[rightChild] > heap[largest])
            largest = rightChild;

        if (largest != index) {
            swap(index, largest);
            heapify(largest);
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public void insert(int value) {
        if (size == heap.length) {
            throw new IllegalStateException("Heap is full");
        }

        int index = size;
        heap[index] = value;
        size++;

        while (index > 0 && heap[index] > heap[parent(index)]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    private int parent(int index) {
        return (index - 1) / 2;
    }

    public void removeMax() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }

        heap[0] = heap[size - 1];
        size--;
        heapify(0);
    }

    public void heapSort() {
        for (int i = size / 2 - 1; i >= 0; i--) {
            heapify(i);
        }

        for (int i = size - 1; i >= 0; i--) {
            swap(0, i);
            heapify(0);
        }
    }

    public static void main(String[] args) {
        int[] array = { 4, 10, 3, 5, 1 };
        BinaryHeapHeapSortExample binaryHeap = new BinaryHeapHeapSortExample(array.length);

        for (int value : array) {
            binaryHeap.insert(value);
        }

        System.out.println("Original array: " + Arrays.toString(array));

        binaryHeap.heapSort();

        System.out.println("Sorted array: " + Arrays.toString(binaryHeap.heap));
    }
}

// Fonte: ChatGPT

O código em Java apresenta a implementação de um Binary Heap e utiliza o algoritmo HeapSort para classificar um array de inteiros em ordem crescente. Vamos entender a lógica principal do código:

  1. A classe BinaryHeapHeapSortExample possui um array heap que representa o Binary Heap e uma variável size que indica o número de elementos presentes no heap.
  2. O método heapify é responsável por garantir a propriedade de heap, ou seja, a ordenação dos elementos no heap. Ele compara o nó atual com seus filhos e faz as trocas necessárias para manter a ordenação correta.
  3. O método insert insere um novo valor no heap. Ele adiciona o valor ao final do array e realiza trocas com o pai, se necessário, para manter a propriedade de heap.
  4. O método removeMax remove o maior elemento do heap, que é sempre o primeiro elemento (índice 0). Ele substitui o primeiro elemento pelo último elemento do array e chama o método heapify para reorganizar o heap.
  5. O método heapSort aplica o algoritmo HeapSort. Ele constrói o heap a partir dos elementos do array, troca repetidamente o elemento máximo (índice 0) com o último elemento não ordenado e chama o método heapify para reorganizar o heap.
  6. No método main, é criado um array de inteiros e um objeto BinaryHeapHeapSortExample. Os valores do array são inseridos no heap e, em seguida, o algoritmo HeapSort é aplicado. Os arrays original e ordenado são exibidos no console.

Exemplo de implementação em Python

Python
class BinaryHeapHeapSortExample:
    def __init__(self):
        self.heap = []
    
    def heapify(self, n, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        if left < n and self.heap[left] > self.heap[largest]:
            largest = left
        
        if right < n and self.heap[right] > self.heap[largest]:
            largest = right
        
        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self.heapify(n, largest)
    
    def insert(self, value):
        self.heap.append(value)
        n = len(self.heap)
        i = n // 2 - 1
        
        while i >= 0:
            self.heapify(n, i)
            i -= 1
    
    def remove_max(self):
        n = len(self.heap)
        
        if n == 0:
            return None
        
        max_value = self.heap[0]
        self.heap[0] = self.heap[n - 1]
        self.heap.pop()
        self.heapify(n - 1, 0)
        
        return max_value
    
    def heap_sort(self):
        n = len(self.heap)
        
        for i in range(n // 2 - 1, -1, -1):
            self.heapify(n, i)
        
        for i in range(n - 1, 0, -1):
            self.heap[i], self.heap[0] = self.heap[0], self.heap[i]
            self.heapify(i, 0)
    

if __name__ == "__main__":
    array = [12, 11, 13, 5, 6, 7]
    heap_sort_example = BinaryHeapHeapSortExample()
    
    for num in array:
        heap_sort_example.insert(num)
    
    print("Array original:", array)
    
    heap_sort_example.heap_sort()
    
    sorted_array = [heap_sort_example.remove_max() for _ in range(len(array))]
    
    print("Array ordenado:", sorted_array)

# Fonte: ChatGPT

Neste código Python, a classe BinaryHeapHeapSortExample implementa um Binary Heap e utiliza o algoritmo HeapSort para classificar um array de inteiros em ordem crescente.

A lógica do código é semelhante à implementação em Java, utilizando métodos como heapify, insert, remove_max e heap_sort para manipular o heap e realizar a ordenação.

No exemplo principal, é criado um array de inteiros e um objeto BinaryHeapHeapSortExample. Os valores do array são inseridos no heap e, em seguida, o algoritmo HeapSort é aplicado. Os arrays original e ordenado são exibidos no console.

Conclusão

Compreender Binary Heap e HeapSort é fundamental para qualquer pessoa interessada em algoritmos e estruturas de dados. Com sua eficiência e versatilidade, esses conceitos são essenciais para resolver problemas complexos de forma eficiente.

Esse conteúdo é parte do material disponibilizado para os participantes do meu grupo de estudos de Algoritmos e Estruturas de Dados. Você quer participar desse grupo? Clique aqui e veja como funciona.

Dúvidas Frequentes

O que é Binary Heap?
Binary Heap é uma estrutura de dados que representa uma árvore binária completa.

O que são Max Heap e Min Heap?
São duas variações de Binary Heap. No Max Heap, os pais têm valores maiores que ou iguais aos dos filhos, enquanto no Min Heap, os pais têm valores menores que ou iguais aos dos filhos.

O que é HeapSort?
HeapSort é um algoritmo de ordenação que utiliza um Binary Heap para ordenar os elementos.

Qual a complexidade de tempo do HeapSort?
A complexidade de tempo do HeapSort é O(n log n), tornando-o eficiente para a ordenação de grandes conjuntos de dados.

Onde o Binary Heap e o HeapSort são aplicados?
Eles são aplicados em muitas áreas, como sistemas de banco de dados, simulação de eventos discretos e algoritmos de caminho mais curto.

Quer se aprofundar neste tema?

Então participe do grupo de estudos de Algoritmos e Estruturas de Dados.

Domine algoritmos e estruturas de dados, torne-se um desenvolvedor de software “além do básico” e diferencie-se no mercado.

Participe do
grupo intensivo de

Algoritmos e Estruturas de Dados

com

Domine algoritmos e estruturas de dados, torne-se um desenvolvedor de software “além do básico” e diferencie-se no mercado.

Participe do
grupo intensivo de

Algoritmos e Estruturas de Dados

com

Domine algoritmos e estruturas de dados, torne-se um desenvolvedor de software “além do básico” e diferencie-se no mercado.

Veja outros artigos relacionados

O Código de Huffman: Uma Transcrição Explicativa

A compressão de dados é um assunto que fascina pela sua capacidade de transformar a maneira como armazenamos e transferimos...

A Relação entre Programação Funcional e Concorrência

A programação funcional vem ganhando espaço na comunidade de tecnologia. Por que isso acontece? Este artigo explora essa popularidade, focando...

Nomes Assustadores para Conceitos Simples

No mundo da tecnologia e da computação, frequentemente nos deparamos com termos que parecem complexos e intimidantes. Vou compartilhar uma...

Programa ElemarJR de
Aceleração de Resultados, do Jeito Certo

Aproveite nossa OFERTA ESPECIAL e adquira o combo completo com acesso a todos os grupos de estudos.

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de DDD do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de DDD do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Padrões de Projeto:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de DDD do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no curso de Binary Heap e HeapSort - O que são e como funcionam:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Reputação e Marketing Pessoal:

Binary Heap e HeapSort – O que são e como funcionam

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no curso de Binary Heap e HeapSort - O que são e como funcionam:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no curso de Binary Heap e HeapSort - O que são e como funcionam:

Mentoria em Arquitetura de Software

Ênfase em Systems Design

Para se candidatar nesta turma aberta, preencha o formulário a seguir:

Reproduzir vídeo

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Algoritmos e Estruturas de Dados:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Algoritmos e Estruturas de Dados:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Padrões de Projeto:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de DDD do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Reputação e Marketing Pessoal:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Padrões de Projeto:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Reputação e Marketing Pessoal:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Reputação e Marketing Pessoal:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Programa ElemarJR de Aceleração, Do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Programa ElemarJR de Aceleração, Do Jeito Certo:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Algoritmos e Estruturas de Dados:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Algoritmos e Estruturas de Dados:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Padrões de Projeto:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Padrões de Projeto:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Reputação e Marketing Pessoal:

Crie sua conta

Preencha os dados a seguir para iniciar o seu cadastro no Grupo Intensivo de Estudos de Algoritmos e Estruturas de Dados:

× Precisa de ajuda?