Estrutura de dados min e max heap

Heap é uma estrutura de dados baseada em árvore binária quase completa, geralmente implementada com um array, usada para acesso eficiente ao menor ou maior elemento.

---

Min-Heap

Definição

• O menor elemento está sempre na raiz.
• Todo nó é menor ou igual aos seus filhos.

Propriedade

pai ≤ filhos

Operações e complexidade

• Inserir (insert): O(log n)
• Consultar mínimo (peek): O(1)
• Remover mínimo (extract_min): O(log n)

Uso típico

• Fila de prioridade (menor valor = maior prioridade)
• Dijkstra, Prim
• Agendamento de tarefas, eventos por tempo

---

Max-Heap

Definição

• O maior elemento está sempre na raiz.
• Todo nó é maior ou igual aos seus filhos.

Propriedade

pai ≥ filhos

Operações e complexidade

• Inserir (insert): O(log n)
• Consultar máximo (peek): O(1)
• Remover máximo (extract_max): O(log n)

Uso típico

• Fila de prioridade (maior valor = maior prioridade)
• Ranking, top-K elementos
• Heapsort (versão clássica usa max-heap)

---

Implementação (conceito)

Geralmente usando array:

• Índice do pai: (i - 1) // 2
• Filho esquerdo: 2*i + 1
• Filho direito: 2*i + 2

A ordem global não é garantida (não é BST); apenas a relação pai ↔ filhos.

---

Comparação rápida

Característica	Min-Heap	Max-Heap
Raiz	Menor elemento	Maior elemento
Prioridade	Menor valor	Maior valor
peek()	O(1)	O(1)
Inserção	O(log n)	O(log n)
Remoção	O(log n)	O(log n)

---

Em entrevistas

• Heap ≠ árvore ordenada
• Heap é ideal quando você precisa do mínimo ou máximo rápido, não de buscas arbitrárias eficientes.

Código

class MinHeap:
    def __init__(self):
        self.heap = []
 
    def insert(self, val):
        self.heap.append(val)
        self._heapify_up(len(self.heap) - 1)
 
    def extract_min(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()  # Move último para raiz
        self._heapify_down(0)
        return root
 
    def _heapify_up(self, index):
        parent = (index - 1) // 2
        if index > 0 and self.heap[index] < self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            self._heapify_up(parent)
 
    def _heapify_down(self, index):
        left = 2 * index + 1
        right = 2 * index + 2
        smallest = index
 
        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
 
        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._heapify_down(smallest)
 
# Teste
h = MinHeap()
for x in [5, 3, 8, 1, 2]:
    h.insert(x)
 
print(h.heap)          # Heap interna
print(h.extract_min()) # 1
print(h.extract_min()) # 2