O quê é uma Heap Binária?
Uma Heap Binária é uma estrutura de dados não linear que implementa uma fila de prioridades usando uma árvore binária completa. Nessa estrutura, cada elemento possui no máximo dois elementos filhos, e o elemento raiz da heap é o maior ou menor elemento de todos, no caso de uma heap de máximo ou de mínimo, respectivamente.
Onde Heaps Binárias são usadas?
- Algoritmos de de Ordenação – Uma Heap Binária é usada para implementar o algoritmo de ordenação Heapsort.
- Roteamento em Grafos – Uma Heap Binária é usada para encontrar o caminho mais curto entre dois nós em um grafo, como no Algoritmo de Dijkstra.
- Gerenciamento de Recursos – Heaps Binários podem ser usados para gerenciar recursos, como memória ou processos, garantindo que as solicitações com a maior prioridade sejam atendidas primeiro.
- Bancos de Dados – Heaps Binários são usados em bancos de dados para implementar índices, otimizar consultas de busca e garantir a consistência de dados em operações de atualização.
Qual é a estrutura de uma Heap Binária?
Uma Heap Binária h pode ser construída com os seguintes componentes:
h.celulas[]: células que armazenam os elementos da heap binária.h.comprimento: um inteiro que conta o número de elementos na heap binária.
Quais são as operações básicas de uma Heap Binária?
Operação Comprimento
- Retorne o valor de
h.comprimento.
Operação Inserir
- Adicionar o novo elemento na folha mais à direita na última camada da árvore.
- Comparar o valor do novo elemento com o valor do seu pai. Se o valor do novo elemento é menor que o valor do pai em uma heap de mínimo, ou se o valor do novo elemento é maior que o valor do pai em uma heap de máximo, troque os dois valores.
- Repita o Passo 2 com o novo elemento até que ele esteja na posição correta na árvore, satisfazendo as propriedades de uma heap binária.
Operação Remover Raiz
O algoritmo para remover o elemento raiz também é conhecido como “extrair o mínimo” ou “extrair o máximo”, em uma heap binária de mínimo ou de máximo, respectivamente.
- Armazene o valor da raiz em uma variável
x. - Substitua o valor da raiz com o valor da folha mais à direita na última camada da árvore.
- Compare o valor do nó com os valores de seus filhos. Se o valor do nó é maior que o valor de algum de seus filhos em uma heap de mínimo, ou se o valor do nó é menor que o valor de algum de seus filhos em uma heap de máximo, troque o valor do nó com o valor do filho de maior prioridade.
- Repita o Passo 3 até que o nó esteja na posição correta na árvore, satisfazendo as propriedades de uma heap binária.
- Retorne o valor armazenado em
x.
Como implementar uma Heap Binária?
Veja o código completo no GitHub.