O que é uma pilha?

Um heap é uma estrutura de dados em forma de árvore especial que satisfaz a propriedade do heap. Esta propriedade afirma que para qualquer vértice, exceto a raiz, o valor da chave desse vértice deve estar em certa relação com o valor da chave do seu pai. Existem dois tipos principais de heaps:

• Max-heap: O valor da chave de cada vértice não é menor que o valor das chaves dos seus filhos. O elemento máximo está na raiz.
• Min-heap: O valor da chave de cada vértice não é maior que o valor das chaves dos seus filhos. O elemento mínimo está na raiz.

O heap geralmente é implementado como um array, o que permite acesso eficiente aos elementos e execução de operações. A relação entre pais e filhos no array é a seguinte:

• Para um elemento com índice i (começando em 0), seu filho esquerdo está no índice 2i + 1.
• Seu filho direito está no índice 2i + 2.
• Seu pai está no índice floor((i - 1) / 2).

Operações principais no heap:

• Inserir: Adicionar um novo elemento. Tempo de execução O(log n), onde n é o número de elementos.
• Extrair Máximo / Extrair Mínimo: Remover e retornar o elemento máximo (em um max-heap) ou mínimo (em um min-heap). Tempo de execução O(log n).
• Heapify (Construção do heap): Transformar um array arbitrário em um heap. Tempo de execução O(n).

Heaps são usados em algoritmos de ordenação (por exemplo, ordenação por heap), em filas de prioridade, e em algoritmos de busca de caminhos mais curtos (por exemplo, o algoritmo de Dijkstra).