Heapify e sift
Passo 1 de 14
Um array cru, não um heap. Consertá-lo nunca mexe no array inteiro: cada valor errado percorre um só caminho.
A ideia
Consertar um heap nunca mexe no array inteiro. Um valor grande demais afunda (sift down) rumo às folhas, trocando de lugar com o filho menor; um valor pequeno demais sobe (sift up) rumo à raiz. Nos dois casos ele percorre um único caminho — no máximo log n trocas.
Para construir um heap a partir de dados soltos, faça o sift down começando pelo último pai e volte para trás. Isso custa O(n), porque a maioria dos nós já está perto da base.
Exemplo do mundo real
O tanque de decantação de uma estação de tratamento de água faz isso sem ninguém mexer. O lodo pesado afunda uma camada por vez até encontrar algo mais pesado; a espuma sobe até encontrar algo mais leve. Nada é comparado com o tanque inteiro — cada partícula só negocia com os vizinhos imediatos.
O código
Sua vez
Coloque os passos em ordem.
- Troque os dois e continue a partir da posição do filho
- Comece pelo último pai, logo acima da linha de baixo
- Vá um índice para a esquerda e repita até terminar o índice 0
- Compare o nó com o menor dos dois filhos dele
Mini quiz
1 / 3