Mound - puzzles online

Em ciência da computação, um heap (monte) (pronuncia-se riːp) é uma estrutura de dados especializada, baseada em árvore, que é essencialmente uma árvore quase completa que satisfaz a propriedade heap: se P é um nó pai de C, então a chave (o valor) de P é maior que ou igual a (em uma heap máxima) ou menor que ou igual a (em uma heap mínima) chave de C. O nó no "topo" da heap (sem pais) é chamado de nó raiz.

O heap é uma implementação maximamente eficiente de um tipo de dados abstrato chamado de fila de prioridade e, de fato, as filas de prioridade são geralmente chamadas de "heaps", independentemente de como elas podem ser implementadas. Em uma heap, o elemento de prioridade mais alta (ou mais baixa) é sempre armazenado na raiz. No entanto, uma heap não é uma estrutura classificada, ela pode ser considerada parcialmente ordenada. Uma heap é uma estrutura de dados útil quando é necessário remover repetidamente o objeto com a prioridade mais alta (ou mais baixa).

Uma implementação comum de uma heap é a heap binária, no qual a árvore é uma árvore binária (veja a figura). A estrutura de dados da heap, especificamente a heap binária, foi introduzida por J. W. J. Williams em 1964, como uma estrutura de dados para o algoritmo de classificação heapsort. Heaps também são cruciais em vários algoritmos de grafo eficientes, como o algoritmo de Dijkstra. Quando uma heap é uma árvore binária completa, ela possui a menor altura possível - uma heap com N nós e, para cada nó, a ramos, sempre possui altura de logaN.

Observe que, conforme mostrado no gráfico, não há ordenação implícita entre irmãos ou primos e nenhuma sequência implícita para um percurso em ordem (como haveria, por exemplo, uma árvore de pesquisa binária). A relação de heap mencionada acima se aplica somente entre nós e seus pais, avós, etc.