Reconhecendo problemas de heap

Um heap é uma árvore binária com uma regra simples que o torna a ferramenta perfeita para uma pergunta recorrente: "qual é o menor (ou o maior) agora?" — respondida em O(1), com inserção e remoção em O(log n).

Como sempre, cada aula de padrão abre com um 🎯 Tente primeiro.

A propriedade do heap

Um min-heap é uma árvore binária completa (preenchida de cima para baixo, da esquerda para a direita) onde todo pai é ≤ seus filhos. Logo, o menor elemento está sempre na raiz (o topo). Um max-heap é o espelho: todo pai ≥ filhos, e o maior fica no topo.

O segredo de implementação: um heap é guardado num array, sem ponteiros. Os filhos do índice i são 2i+1 e 2i+2; o pai de i é (i-1)//2. Por isso a árvore-heap e o array são a mesma coisa.

As operações: O(log n) e O(1)

Push (sift-up): coloque o novo elemento na última posição e deixe-o subir, trocando com o pai enquanto for menor que ele. Como a árvore tem altura log n, são no máximo log n trocas. Veja os elementos bolharem para cima:

Pop (sift-down): o topo sai; o último elemento vai para a raiz e desce, trocando com o menor filho até a propriedade voltar. De novo, no máximo log n passos (a altura). Observe o topo sair e o heap se reorganizar — repare que os valores saem em ordem crescente:

Quando o heap é a ferramenta certa

O heap brilha quando você precisa do extremo (mínimo/máximo) repetidamente, mas não precisa de tudo ordenado:

• "Os K maiores/menores" — um heap de tamanho K (próxima aula).
• "O próximo menor entre várias fontes" — k-way merge.
• "A mediana de um fluxo" — dois heaps.
• Filas de prioridade: agendadores, Dijkstra (grafos), Huffman.

Por que não simplesmente ordenar? Ordenar é O(n log n) e te dá tudo em ordem — exagero se você só quer os K maiores ou o mínimo atual. Para um fluxo que muda, reordenar a cada passo seria caríssimo; o heap ajusta em O(log n). E o n & (n-1)... opa, esse era de bits. 😄

Heap na prática: Python tem, JavaScript não

Em Python, use o módulo heapq (um min-heap pronto). Em JavaScript, não há heap nativo — você implementa uma classe pequena (ou usa os índices 2i+1/2i+2 direto num array). Veja os dois extraindo em ordem crescente:

(Para um max-heap em Python, empurre valores negados; em JS, troque o comparador para (a, b) => b - a.)

Os problemas da seção

• Kth Largest, Top K Frequent → heap de tamanho K
• Merge k Sorted Lists → k-way merge (revisita a seção Lista Ligada!)
• Find Median from Data Stream → dois heaps

Resumo

• Heap = árvore binária completa num array; min no topo (min-heap) ou max no topo (max-heap).
• peek O(1), push/pop O(log n) (sift-up/down sobem/descem a altura log n), heapify O(n).
• Use quando precisar do extremo repetidamente sem ordenar tudo.
• Python: heapq. JavaScript: implemente (índices 2i+1/2i+2).

Próxima aula: pegar os K maiores sem ordenar tudo.