Definição - o que significa Heap?
Um heap, no contexto da estrutura de dados, é uma estrutura de dados baseada em árvore que satisfaz a propriedade heap, em que cada elemento é atribuído a um valor-chave ou peso. A chave de valor inferior sempre tem um nó pai com uma chave de valor superior. Isso é chamado de estrutura de heap máximo e, entre todos os nós, o nó raiz tem a chave mais alta.
Às vezes, uma estrutura baseada em árvore tem uma regra de estrutura reversa, em que um elemento com uma chave de valor superior sempre tem uma chave de valor inferior como nó pai. Isso é chamado de estrutura de heap mínimo e, entre todos os nós, o nó raiz tem a chave mais baixa.
Definirtec explica Heap
Não há restrições práticas quanto ao número de filhos que cada nó pode ter em um heap, embora cada nó geralmente tenha dois, no máximo. O heap é considerado a implementação mais eficiente de um tipo de dado abstrato, conhecido como fila de prioridade. A implementação de heap é essencial em vários algoritmos de gráfico (incluindo o algoritmo de Dijkstra), bem como no algoritmo de classificação de heapsort.
Heaps têm várias variações que agem como implementações de fila de prioridade de tipo de dados abstratos com alta eficiência. Muitos aplicativos, como algoritmos de gráfico, requerem a implementação de filas prioritárias.
Uma matriz é a forma de implementação mais comum de heap, onde nenhum ponteiro é necessário para vincular seus elementos.
Heaps realizam várias operações, incluindo:
- Find-max: Procura o nó-chave mais alto entre um grupo de nós
- Find-min: Procura o nó-chave mais baixo entre um grupo de nós
- Delete-max: Exclui o nó-chave mais alto entre um grupo de nós
- Delete-min: Exclui o nó-chave mais baixo entre um grupo de nós
Heaps também incluem funções que realizam fusão, inserção e alterações de chave.
Esta definição foi escrita no contexto da Estrutura de Dados