O que é uma pilha (no contexto de estruturas de dados)?

Um heap é uma árvore especializada usada como estrutura de dados. A principal propriedade do heap é a ordenação parcial: para qualquer vértice, a condição é que o valor do vértice pai seja maior ou igual ao valor de qualquer um de seus filhos (max-heap) ou menor ou igual (min-heap).

Características principais:

• Árvore binária: Geralmente implementada como uma árvore binária, onde cada nó tem no máximo dois filhos.
• Árvore binária completa: Em todos os níveis, exceto possivelmente o último, a árvore está completamente cheia. Os nós no último nível são preenchidos da esquerda para a direita. Isso permite armazenar eficientemente o heap em forma de array.
• Propriedade do heap:
  • Max-heap: O valor de cada nó é maior ou igual ao valor de seus filhos. O elemento máximo está sempre na raiz.
  • Min-heap: O valor de cada nó é menor ou igual ao valor de seus filhos. O elemento mínimo está sempre na raiz.

Operações principais com o heap:

• Inserção de elemento: Adicionar um novo elemento e manter a propriedade do heap.
• Remoção de elemento: Remover o elemento da raiz (máximo ou mínimo, dependendo do tipo de heap) e manter a propriedade do heap.
• Construção do heap: Construir um heap a partir de um array de elementos.

Aplicações do heap:

• Ordenação: Algoritmo de ordenação por heap (Heapsort).
• Filas de prioridade: Implementação eficiente de filas onde os elementos são processados em ordem de prioridade.
• Algoritmos de busca: Por exemplo, busca do k-ésimo elemento por valor.
• Algoritmos em grafos: Por exemplo, o algoritmo de Dijkstra.

Representação do heap em array:

Como o heap é uma árvore binária completa, pode ser armazenado eficientemente em um array sem usar ponteiros.

• Se um nó está no índice i, seu filho esquerdo está no índice 2*i + 1.
• Seu filho direito está no índice 2*i + 2.
• Seu pai está no índice (i - 1) / 2.

# Exemplo de representação de min-heap em forma de array
heap_array = [10, 15, 20, 17, 25, 30]

# Raiz: heap_array[0] = 10
# Filho esquerdo da raiz: heap_array[2*0 + 1] = heap_array[1] = 15
# Filho direito da raiz: heap_array[2*0 + 2] = heap_array[2] = 20
# Pai do elemento no índice 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15