Este é o segundo artigo da série de estruturas de dados anunciada no fim do texto sobre pilhas e filas. O protagonista é o heap, mas antes precisamos esclarecer um mal-entendido.
No artigo relacionado Guia completo de pilhas e filas: por que o Swift não tem um tipo Stack (incluindo a armadilha do removeFirst), você pode conferir os conceitos básicos e os casos de aplicação relacionados.
**O heap de estrutura de dados só compartilha o nome com o heap de memória; não há relação entre eles.**A área de heap da memória é um espaço de alocação dinâmica; o heap deste artigo é «uma árvore para extrair o menor (ou maior) valor em O(1)».
A diferença entre as áreas de alocação de memória é explicada separadamente em Pilha vs heap. Aqui, o foco é apenas Heap e Priority Queue como estruturas de dados.
Se você esperava o heap do artigo sobre pilha vs heap, este é um mundo completamente diferente.
O problema que o heap resolve é claro.
«Quero processar primeiro o que é mais urgente, mas ordenar tudo antes seria desperdício.»
Ordenar é exagero
Imagine uma fila que remove primeiro a tarefa de maior prioridade. Ordenar o array toda vez custa O(n log n) a cada inserção.
Mesmo mantendo a ordem e procurando a posição de inserção, mover elementos custa O(n).
Pensando bem, não precisamos que tudo esteja ordenado. Basta saber imediatamente qual é o item mais urgente.
Podemos descobrir quem está em segundo lugar depois que o primeiro sair, sem problema.
É exatamente isso que o heap promete. Por isso, tanto a inserção quanto a remoção terminam em O(log n).
«Quanto menos você promete, mais rápido fica» é um trade-off clássico no projeto de estruturas de dados.
Regra do heap: o pai é menor que os filhos; só isso
Um heap mínimo é uma árvore binária completa com uma única regra.
Todo pai é menor ou igual aos próprios filhos.
Não importa qual irmão é maior. A subárvore esquerda também não precisa ser menor que a direita.
Basta respeitar a relação entre pai e filho. Graças a essa flexibilidade, a raiz sempre contém o menor valor global, mas nada além disso é garantido.
Inserção (sift up): adiciona no fim da árvore e, se for menor que o pai, troca e sobe. Como percorre apenas a altura da árvore, custa O(log n).
Extração do menor valor (sift down): remove a raiz, leva o último elemento para ela e desce trocando-o com o menor dos dois filhos. Também custa O(log n).
A mágica de criar uma árvore com um array
É aqui que a implementação do heap fica elegante. Como a árvore binária completa é preenchida da esquerda para a direita, podemos colocá-la em ordem no array sem ponteiros.(NIST Heap).
Índice: 0 1 2 3 4 5
Valor: [1, 3, 2, 7, 4, 5]Os relacionamentos familiares aparecem apenas com o cálculo dos índices.
- Pai:
(i - 1) / 2 - Filho esquerdo:
2i + 1, filho direito:2i + 2
Não há objetos de nó, ponteiros para filhos nem alocação de memória no heap. Aproveitamos a localidade de cache discutida em array vs lista encadeada e usamos apenas a estrutura lógica da árvore.
Em Swift, o esqueleto fica assim.
struct MinHeap<Element: Comparable> {
private var elements: [Element] = []
var min: Element? { elements.first } // O(1)
mutating func insert(_ value: Element) { // O(log n)
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func removeMin() -> Element? { // O(log n)
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let min = elements.removeLast()
siftDown(from: 0)
return min
}
}siftUp/siftDown são as trocas repetidas explicadas acima.
Por sinal, transformar um array existente inteiro em heap com build-heap não é O(n log n) por inserir cada elemento. Fazendo sift down a partir da metade inferior, termina em O(n) — um detalhe comum em entrevistas.
O lugar do heap na prática
**Uma fila de prioridade é um heap.**Usando a expressão do artigo sobre pilhas e filas, a fila remove por ordem de chegada, a fila de prioridade por urgência, e o heap é sua implementação padrão (NIST Priority Queue).
- Escalonador do SO: atribui a CPU primeiro aos processos de maior prioridade
- Menor caminho de Dijkstra: algoritmo que remove repetidamente «o caminho mais curto encontrado até agora»; sem heap, o desempenho desaba
- Gerenciamento de timers: estrutura interna que só precisa saber qual timer, entre muitos, tocará primeiro
- Heapsort: inserir e remover tudo produz uma ordenação O(n log n). A vantagem é ordenar in-place sem memória extra
- Problema Top-K: «manter os K maiores de um fluxo» — resolvido em O(n log K) com um heap mínimo de tamanho K. É um padrão frequente em testes de programação
A biblioteca padrão do Swift não tem heap. Assim como o Deque do artigo sobre pilhas e filas, o pacote da Apple swift-collections fornece Heap (swift-collections Heap).
Esta implementação de min-max heap oferece min e max em O(log n). Em ambientes sem pacotes externos, como testes de programação, é prático dominar o esqueleto MinHeap acima.
Resumo
- O heap de estrutura de dados só tem o mesmo nome que o heap de memória — é «uma árvore que extrai o menor valor instantaneamente»
- A única regra é pai ≤ filho — abrir mão da ordenação total reduz inserção e remoção a O(log n)
- Por ser uma árvore binária completa, pode sercolocada em um array sem ponteiros — pai
(i-1)/2, filhos2i+1,2i+2 - O heap é a implementação padrão da fila de prioridade; Dijkstra, escalonadores e Top-K são usos representativos
- No Swift, swift-collections oferece
Heap; em testes de programação, implementar diretamente é o padrão
A próxima parte será sobre tabelas hash: como o Swift Dictionary obtém O(1) e o verdadeiro significado do que Hashable exige.
Fontes e verificação
- swift-collections HeapApple · Documentação oficial · Consultado 17 de agosto de 2026Evidência: API Heap do Swift e comportamento de heaps mínimo e máximo
- NIST Dictionary of Algorithms: Priority QueueNIST · Dados oficiais · Consultado 17 de agosto de 2026Evidência: Definição do tipo abstrato de dados de uma fila de prioridade
- NIST Dictionary of Algorithms: HeapNIST · Dados oficiais · Consultado 17 de agosto de 2026Evidência: Estrutura e características operacionais de um heap baseado em arrays