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#
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: ChatGPTO 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
BinaryHeaprepresenta a estrutura do Binary Heap. Ela possui um array interno chamadoheapque armazena os elementos e uma variávelsizeque 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
RemoveMaxremove o elemento máximo (raiz) do Binary Heap e o substitui pelo último elemento do heap. Em seguida, ele chama o métodoHeapifypara restaurar a propriedade de heap. - O método
HeapSortutiliza 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
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: ChatGPTO 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:
- A classe
BinaryHeapHeapSortExamplepossui um arrayheapque representa o Binary Heap e uma variávelsizeque indica o número de elementos presentes no heap. - 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. - O método
insertinsere 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. - O método
removeMaxremove 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étodoheapifypara reorganizar o heap. - O método
heapSortaplica 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étodoheapifypara reorganizar o heap. - No método
main, é criado um array de inteiros e um objetoBinaryHeapHeapSortExample. 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
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: ChatGPTNeste 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.
