Pular para o conteúdo

Heapify e sift

Aula 2 de 7 · 6 min

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.

  1. Troque os dois e continue a partir da posição do filho
  2. Comece pelo último pai, logo acima da linha de baixo
  3. Vá um índice para a esquerda e repita até terminar o índice 0
  4. Compare o nó com o menor dos dois filhos dele

Mini quiz

1 / 3

Em um min-heap, como se move um valor grande demais para a posição dele?