Pular para o conteúdo
Entrar Criar conta

Algoritmos e estruturas de dados · Estruturas de dados · 5 min de leitura

Heaps e filas de prioridade

O menor (ou maior) sempre no topo, com inserção e remoção em O(log n): a estrutura por trás de agendadores, top-k, Dijkstra e do heapsort — guardada num simples array.

2 → 5: 2 < 5: troca15 → 1: 2 > 1: para2 > 1: para21 → 33 → 73 → 95 → 81 — raiz [0]1raiz [0]3 — [1]3[1]5 — [2] → desce5[2] → desce7 — [3]7[3]9 — [4]9[4]8 — [5]8[5]2 — novo [6] → sobe2novo [6] → sobe

Arraste para o lado para ver o diagrama inteiro.

O 2 entra na primeira vaga livre (índice 6), troca com o pai 5 (passo 1) e para porque o novo pai, 1, é menor (passo 2). No máximo uma troca por nível: O(log n).

A regra do heap

Num min-heap, cada pai é menor ou igual aos filhos; logo o menor de todos está na raiz e ler o topo é O(1). Não é uma árvore ordenada como a BST — irmãos não têm ordem entre si —, e é exatamente essa folga que deixa inserir e remover baratos: O(log n).

Um array disfarçado de árvore

O heap é guardado num array, sem ponteiros. Com índices começando em 0, os filhos de i ficam em 2i + 1 e 2i + 2, e o pai em (i − 1) / 2. Inserir: coloca no fim e sobe. Remover o topo: põe o último no lugar da raiz e desce trocando com o menor filho.

Onde aparece

  • PriorityQueue (Java/Kotlin) e Heap do Swift Collections.
  • Agendadores de tarefas e timers (o próximo a vencer no topo).
  • Top-k: os k maiores de n itens com um heap de tamanho k, O(n log k).
  • Dijkstra (menor caminho) e intercalar k listas ordenadas.

No código: antes e depois

✗ AntesKotlin
// O(n log n): ordena tudo só para pegar k itens
fun topK(vendas: List<Int>, k: Int) = vendas.sortedDescending().take(k)
✓ DepoisKotlin
import java.util.PriorityQueue

// O(n log k): um min-heap guarda só os k maiores vistos até agora
fun topK(vendas: List<Int>, k: Int): List<Int> {
    val heap = PriorityQueue<Int>() // menor no topo
    for (v in vendas) {
        heap.add(v)
        if (heap.size > k) heap.poll() // descarta o menor dos k + 1
    }
    return heap.sortedDescending()
}

Com 10 milhões de vendas e k = 10, o heap nunca passa de 11 itens: pouca memória e cada operação custa uns 4 passos.

Em resumo

Exercícios

Responda e confira na hora. Complexidades valem com ou sem espaços, como O(n log n).

  1. Num min-heap, onde fica o menor elemento?

    Ver a solução

    Resposta: na raiz. Cada pai é menor ou igual aos filhos, então o menor de todos sobe até a raiz (índice 0 do array).

  2. Num heap guardado em array (índices a partir de 0), quais são os índices dos filhos do nó 2? Responda como "5 e 6".

    Ver a solução

    Resposta: 5 e 6. Filhos de i: 2i + 1 = 5 e 2i + 2 = 6.

  3. Qual a complexidade de achar os k maiores de n itens com um min-heap de tamanho k?

    Ver a solução

    Resposta: O(n log k). Cada um dos n itens faz uma inserção (e talvez uma remoção) num heap de tamanho k: O(log k) cada.

Perguntar à IA

Monte um prompt pronto sobre Heaps e filas de prioridade na sua linguagem e no seu caso, e abra num chat gratuito.

ChatGPT Claude Perplexity

O prompt vai para o site que você escolher. Não cole senhas, tokens nem dados reais de clientes. Para Gemini e outros, copie e cole.

Referências

Continue aprendendo

Todos os temas de algoritmos e estruturas de dados →