24 de Março
Heap
O que é um heap, por que ele ajuda quando o menor ou maior item importa mais que a ordenação completa, e onde ele aparece em entrevistas.
O que é
Heap é uma estrutura pensada para acessar rápido o maior ou o menor item.
Ela não mantém tudo totalmente ordenado.
Ela mantém o topo fácil de pegar.
Quando usar
Heap costuma encaixar quando o problema pede:
- maior ou menor elemento repetidamente
- top-k
- prioridade
Se você só quer o próximo item mais importante, ordenar tudo pode ser trabalho demais.
Erro comum
O erro clássico é pensar em heap como “array meio estranho”.
O ponto não é a representação.
O ponto é a operação barata no topo.
Pergunta melhor
Antes de aplicar, vale perguntar:
- eu preciso do conjunto inteiro ordenado?
- ou só preciso tirar o próximo maior/menor várias vezes?
- uma priority queue descreve melhor o problema?
Compartilhar esta página
Copie o link manualmente no campo abaixo.