Heap

O que é um heap

Um heap é uma binary tree com uma regra: todo node é menor que os dois children dele. O que importa é o que isso deixa de fora — a regra não diz nada sobre como um node se compara ao sibling, ao primo, ou a qualquer coisa que não esteja diretamente acima ou abaixo dele.

A regra fixa exatamente uma coisa: o menor valor fica na root, onde você lê sem procurar. Todo o resto fica deliberadamente vago, e é dessa vagueza que este artigo trata.

Olhe a figura mais uma vez: 20 está mais fundo na tree que 25, e é menor. Numa Binary Search Tree isso seria um defeito. Aqui é uma informação que a estrutura nunca prometeu ter.

O problema que uma Binary Search Tree não resolvia

O artigo anterior terminou numa estrutura que responde "onde está este valor" em O(log n) garantido, mantém tudo ordenado e suporta range queries. Ela é excelente, e é muito mais do que você precisa se sua única pergunta é "qual é o menor agora".

Uma balanced BST mantém uma ordenação total — a relação de cada valor com todos os outros está implícita na posição dele. Isso custa dois pointers por node, uma passada de rebalanceamento em toda escrita, e um layout de memória espalhado onde cada passo de um lookup é um cache miss. Se tudo que você faz é pegar o mínimo e adicionar valores novos, você está pagando por um ranking completo e lendo uma entrada dele. Pior: o mínimo de uma BST é o node mais à esquerda, então até ler custa O(log n).

Então: quanto da ordenação dá para jogar fora e ainda responder "qual é o menor"? Quase tudo.

Priority Queue é o ADT, heap é a estrutura

Os dois nomes são usados de forma intercambiável, e não são o mesmo tipo de coisa.

Uma Priority Queue é um tipo abstrato de dados. Ela define operações e o comportamento delas, e não diz nada sobre memória: insert(value), extract-min() e peek(). Esse é o contrato. É a queue de antes na série com a regra FIFO trocada — em vez de o item mais antigo sair primeiro, sai o mais urgente.

Note que não há search, nem iterar em ordem, nem pegar o terceiro menor — uma Priority Queue que não faz isso não está incompleta; isso nunca esteve no contrato. Várias estruturas concretas satisfazem o contrato, com perfis de custo bem diferentes:

Os dois arrays são os extremos, e os dois são ruins: um torna a inserção grátis e a extração linear, o outro faz o inverso. A balanced BST é respeitável em tudo e a melhor em nada. O Fibonacci heap tem a melhor assintótica no papel e constantes ruins o bastante para quase nada usar. O binary heap é logarítmico nas duas escritas e constante na leitura, usando um array plano e nenhum pointer.

A invariante, e tudo que ela não diz

A invariante do heap é uma afirmação sobre edges, não sobre a tree — para todo node i, value[i] <= value[2i+1] e value[i] <= value[2i+2], e nada além disso.

A invariante da BST é uma afirmação sobre subtrees inteiras: tudo à esquerda é menor, tudo à direita é maior, até o fim. Ela restringe um node contra n outros valores; a regra do heap o restringe contra dois.

Então um heap é radicalmente subdeterminado. Sete valores distintos formam 80 min-heaps legais. Aqui estão dois deles.

Só a root coincide, e não é coincidência — é a única posição que a invariante determina. Fixe a forma de uma BST e aqueles sete valores têm um arranjo legal; um heap tem oitenta. Essa frouxidão é a fonte da velocidade do heap: uma estrutura que restringe menos tem menos a consertar quando muda.

É também por isso que você não consegue ler um heap em ordem. Nenhuma passada única sobre o array devolve saída ordenada, porque a informação de ordenação genuinamente não está lá. Consegui-la significa extrair o mínimo repetidamente, o que custa O(n log n) e destrói o heap. Iteração ordenada, range queries, "ache o valor mais próximo de x" — nada disso está disponível. Esse é o preço, visto do outro lado: o heap é rápido porque nunca comprou nada disso.

Completa por construção

Como a invariante não diz nada sobre qual slot um valor ocupa — só sobre a relação de um slot com os dois abaixo dele — o heap é livre para escolher a própria forma. Então ele escolhe a melhor: se mantém uma binary tree complete, todo level cheio exceto possivelmente o último, que preenche da esquerda para a direita.

Ninguém mantém isso deliberadamente. Cai das duas operações: a inserção anexa na primeira posição livre, a remoção tira a última ocupada, e nenhuma das duas deixa buraco no meio. E uma tree complete, como o artigo de binary trees mostrou, é exatamente onde a representação em array sai de graça:

Aquele artigo avisava que a mesma representação é catastrófica numa tree degenerate — 21 nodes em cadeia precisariam de dois milhões de slots. Um heap nunca pode ser degenerate, então ele cai no caso grátis toda vez.

O que faz do desenho acima uma mentira de conveniência: não existe tree nenhuma. Sem nodes, sem campo Left, sem campo Right, sem alocações. Existe um slice contíguo de inteiros, e a tree é um jeito de pensar sobre a aritmética. O diagrama no playground abaixo é uma visão; o array embaixo dele é a estrutura.

Sift up e sift down

As duas operações de escrita funcionam igual: ponha o valor no único slot que mantém a tree complete, e deixe ele se mover por um único caminho root-até-leaf até a invariante voltar a valer. Um valor se move, no máximo log n levels.

Insert faz sift up

Anexe no fim do array — o primeiro slot livre — e troque com o parent enquanto o valor novo for menor. Inserindo 5 acima, ele cai no índice 7 como child de 40.

Agora 5 sobe. Menor que 40, trocam; menor que 25, trocam; menor que 10, trocam. Três comparações, três swaps, e ele para na root.

Só um caminho root-até-leaf foi tocado. Nada na subtree direita foi sequer lido — o resto do heap não precisa saber que houve uma inserção.

Extract-min faz sift down

O mínimo está na root, então lê-lo é de graça. Removê-lo deixa um buraco no índice 0, e o conserto é mover o último elemento para a root e deixá-lo afundar. A cada level ele compara com os dois children e troca com o menor, parando quando os dois forem maiores.

Extraindo do heap que acabamos de montar: 5 sai da root, 40 sobe do fim, e então afunda passando 10 e 25 até o índice 3.

Promover o child menor seria o conserto óbvio — ele já é o próximo menor valor, então a invariante valeria imediatamente — e é o movimento errado. Ele desloca o buraco um level para baixo em vez de removê-lo, e repetir isso deixa uma lacuna no meio da última fileira. A tree deixa de ser complete e a aritmética de índice quebra: 2i+1 só aponta para um child real se todo slot anterior estiver preenchido. Promover o último elemento custa duas comparações a mais por level, e em troca o array fica denso para sempre.

Representando um heap na memória

Não existe node type aqui, que é a forma mais curta de dizer tudo acima.

Repare no que está ausente. Sem struct Node, sem checagem de nil, sem recursão, sem alocação além do slice crescendo — Push e Pop são um loop sobre um índice cada. A estrutura mais compacta da série, por exatamente uma razão: a invariante é fraca o bastante para a posição ser calculada em vez de armazenada.

Teste você mesmo

O array é a estrutura e a tree é uma visão dele, então o playground mostra os dois e move os dois juntos. Insira um valor e veja ele cair no slot ghost no fim antes de subir; extraia e veja o último elemento ser promovido à root e afundar.

Insira um valor menor que tudo que está lá e ele viaja até a root, destacando a única parte da estrutura que foi tocada. Depois insira um valor grande e veja ele parar depois de uma única comparação — é disso que a próxima seção depende.

Construindo um heap a partir de um array

Suponha que você já tem n valores e quer um heap. Existem dois jeitos, e a distância entre eles é o fato mais citado sobre heaps — e o mais citado sem a ressalva.

Insira um por vez, a O(log n) cada, dando O(n log n). Ou ponha todos no array como estão e faça sift down do último node interno de volta até a root, o que é O(n): sift down é barato onde os nodes são numerosos — metade de todos os nodes são leaves e não podem se mover, um quarto pode mover um level, só a root pode mover log n — e essa soma converge para uma constante vezes n.

Três sift downs transformam isso em [10, 25, 15, 30, 40, 50, 20], com todo leaf pulado — num heap grande, metade do array intocada. Até aqui, o de sempre: use o build bottom-up. A conclusão está certa; o raciocínio que costuma vir junto não está.

O que a medição diz

Instrumentei os dois builds para contar comparações, em entrada aleatória e em entrada descendente — descendente sendo o caso adversarial da inserção, já que todo valor que chega bate tudo que já está no heap e sobe até a root.

Comparações por elemento. Leia as colunas, não as linhas.

O build bottom-up é plano — 1,7 a 2,0 por elemento ao longo de uma faixa de 256× de tamanhos, e indiferente a se a entrada é aleatória ou adversarial. É isso que O(n) parece quando você mede.

O build por inserção é onde o folclore engana. Em entrada aleatória ele custa 2,27 por elemento em n = 16.384, contra um log₂ n de 14 — não é n log n de nenhum jeito que você consiga detectar, e é mal pior que o build bottom-up. A razão está visível no playground: um valor escolhido ao acaso costuma ser maior que o parent dele, então para depois de uma comparação. O log n por insert é um pior caso que dados aleatórios quase nunca alcançam. Em entrada descendente ele custa 12,00, acompanhando log₂ n com margem de dois. Aí está o n log n, e ele só aparece quando a entrada chega ordenada do jeito errado.

Heapsort

Construa um heap em O(n), e então extraia o mínimo n vezes a O(log n) cada. A saída sai ordenada, dando O(n log n) no total.

A parte elegante é que não precisa de memória extra. A extração encolhe o heap em um slot no fim do array, e esse slot é exatamente onde o valor extraído vai — então o array ordena de trás para frente enquanto o heap encolhe pela frente. Espaço extra O(1) de verdade, que o mergesort não oferece e o quicksort só consegue com cuidado, mais um pior caso que entrada nenhuma degrada.

Mesmo assim quase nada usa heapsort como sort principal, por duas razões.

Ele não é estável. Dois valores iguais podem sair na ordem inversa da que entraram, porque o sift os troca pelo array sem considerar de onde começaram. Se você ordena registros por um campo e espera que empates mantenham a ordem anterior, o heapsort quebra isso silenciosamente.

O padrão de acesso à memória é hostil. Todo sift down salta do índice i para 2i+1, então quanto mais fundo num array grande você vai, mais distantes ficam acessos consecutivos. O quicksort varre linearmente e é bem mais amigável ao cache — o suficiente para vencer na prática apesar do pior caso O(n²).

Por isso a maioria das bibliotecas padrão entrega introsort: quicksort, trocando para heapsort se a recursão passar de 2 log n levels. O heapsort está na função de sort da sua linguagem — como paraquedas, não como motor.

Operações comuns e seus custos

As quatro primeiras linhas são por que heaps existem; as duas últimas são o que eles custam. Leia a quarta contra a sexta: um heap é construído em tempo linear justamente porque nunca chega a estar ordenado — e essa mesma falta é por que tirar saída ordenada de volta custa O(n log n). Um trade só, visto duas vezes.

Heaps no mundo real

Schedulers e timers

O próprio runtime do Go mantém os timers pendentes de cada processador num min-heap, então "qual dispara a seguir" é uma leitura em tempo constante. Ele usa um heap 4-ário em vez de binário — quatro children por node, então a tree é mais rasa e um sift down faz mais comparações em menos levels, o que agrada o cache. O asyncio do Python agenda seus callbacks com heapq. Todo sistema com trabalho agendado tem essa forma — cron, uma fila de jobs, um rate limiter, uma simulação de eventos discretos, os eventos temporizados de uma game engine. Muita coisa esperando, uma pergunta, feita o tempo todo.

Top-k sem ordenar

Para achar os 10 maiores valores num stream de um bilhão, mantenha um min-heap de tamanho 10: para cada valor novo, compare com a root, e se for maior substitua a root e faça sift down. Você termina com o top 10 em tempo O(n log k) e espaço O(k), sem nunca guardar o stream.

A parte contraintuitiva é usar um min-heap para rastrear máximos. A root ser o menor dos seus dez melhores é exatamente o que você precisa, porque é ele que deve ser descartado.

Caminhos mínimos

O algoritmo de Dijkstra e o A* funcionam pegando repetidamente o node não visitado mais próximo, o que é uma priority queue por definição. Este é o lugar mais comum onde um programador encontra um heap deliberadamente, e onde os algoritmos de graph vão retomar a história mais adiante.

Sua linguagem já entrega um

Go tem container/heap, que fornece a lógica do sift assim que você fornece cinco métodos: Len, Less e Swap, mais um Push e um Pop que o package chama no seu slice — não os que você chama, que é o detalhe onde as pessoas tropeçam. Python tem heapq, sobre uma list comum. Java tem PriorityQueue, C++ tem priority_queue, e Rust tem BinaryHeap — um max-heap, então min-heap significa embrulhar os valores em Reverse.

Quando Heaps deixam a desejar

Não existe search. Achar um valor qualquer é O(n), porque a invariante não oferece direção nenhuma em node nenhum. Precisar de "x está aqui?" além de "qual é o mínimo" significa um segundo índice ao lado do heap.

Atualizar um elemento qualquer precisa de ajuda. Decrease-key — baixar a prioridade de um valor — é o que Dijkstra de fato quer, e é O(log n) se você já souber o índice do elemento. Achar esse índice é o search O(n) de cima. Implementações reais mantêm um map separado de valor para índice e o atualizam a cada swap, o que é chato e é a fonte mais comum de bugs em heaps escritos à mão.

Só uma ponta é rápida. Um min-heap responde "qual é o menor" em O(1) e "qual é o maior" em O(n) — o máximo está em algum lugar entre os leaves. Precisar dos dois significa um min-max heap, ou dois heaps mantidos em equilíbrio, que é o truque padrão para uma mediana corrente.

Sem ordenação, sem ranges. Tudo que os dois artigos anteriores ofereciam — iteração ordenada, BETWEEN, successor e predecessor — sumiu. Se você precisa disso e de acesso rápido ao mínimo, uma balanced BST dá os dois.

Fundir dois heaps é lento. Combinar dois binary heaps de tamanho n significa reconstruir, a O(n); binomial, pairing e leftist heaps são feitos para isso e fundem em O(log n).

Resumo

Um heap é o que você obtém quando guarda só a parte da ordenação que responde uma pergunta:

• A invariante é só parent contra child — nada entre siblings, nada entre subtrees, e é por isso que sete valores formam 80 heaps legais e só a root fica fixada
• Fraca o bastante para ser sem forma, então a forma pode ser escolhida — as operações mantêm a tree complete sem tentar, e é exatamente aí que a representação em array não custa nada
• Não existe tree nenhuma — um slice contíguo, com 2i+1, 2i+2 e (i−1)/2 no lugar de todo pointer
• Insert faz sift up, extract faz sift down — um valor se move por um caminho root-até-leaf, no máximo log n levels, sem tocar em mais nada
• O último elemento é promovido no extract, não o child menor, porque é a única escolha que não deixa buraco
• Construir bottom-up é O(n) — menos de 2 comparações por elemento independentemente de tamanho ou ordem de entrada, enquanto a inserção só degrada para log n em entrada adversarial
• Heapsort é in-place e garantido, e não é estável — por isso ele entra como paraquedas do introsort e não como sort padrão

O insight para levar adiante é que esta é a primeira estrutura da série que ficou mais rápida prometendo menos. Todo artigo anterior adicionou uma restrição para comprar uma capacidade: ordenação para permitir busca, balanceamento para limitar a height. O heap vai na direção oposta e sai com um mínimo em tempo constante, um build em tempo linear e nenhum pointer. Quando uma estrutura parece cara, a pergunta produtiva muitas vezes não é como acelerá-la, e sim quais das garantias dela você nunca estava usando.

Isso fecha a série de árvores. Ela abriu com uma tree sendo nada além de um jeito de dar a um node mais de um next; ela acabou sendo a forma por trás de ordered maps, índices de banco, schedulers e priority queues. O próximo artigo derruba as duas últimas restrições — um parent por node, e nada de cycles — e pergunta o que sobra quando um node pode apontar para qualquer coisa.