What is a Heap?
Lição 2 de 14 do curso Heaps e Filas de Prioridade - Série de Estruturas de Dados #7 da Coddy.
Um heap é uma estrutura de dados em forma de árvore que obedece a uma invariante simples: cada pai é menor que (ou igual a) seus filhos. O menor valor sempre fica na raiz, pronto para ser lido em O(1). Esse tipo específico é chamado de min-heap; a imagem espelhada com uma invariante de maior-na-raiz é um max-heap.
A parte inteligente é o armazenamento. Embora pensemos nele como uma árvore, um heap reside em um array linear. Para o nó no índice i:
- Seu pai está no índice
(i - 1) / 2. - Seu filho à esquerda está no índice
2 * i + 1. - Seu filho à direita está no índice
2 * i + 2.
Sem ponteiros, sem objetos de nó: apenas matemática de índices. Isso torna os heaps muito amigáveis ao cache e fáceis de implementar.
As cinco principais operações em um min-heap são:
- Peek: Retorna o menor valor (a raiz).
- Insert: Adiciona um valor e o move para cima (bubble up) até seu lugar.
- ExtractMin: Remove e retorna o menor valor.
- Size: Retorna quantos valores estão armazenados.
- IsEmpty: Verifica se o heap está vazio.
Vamos criar uma classe MinHeap!
Experimente você mesmo
Esta lição não inclui um desafio de código.
