Heapify in-place de uma lista
A missão
Problema
Rearranje uma lista de números em um min-heap in-place, sem o módulo heapq, e retorne-a. Em um min-heap guardado em uma lista, os filhos do índice i ficam em 2i + 1 e 2i + 2, e todo pai é menor ou igual a cada um dos seus filhos. Use o método bottom-up: aplique sift down em cada pai, começando pelo último pai e indo em direção à raiz, para que a construção inteira rode em O(n).
Exemplos
Input: nums = [5, 3, 8, 1, 2]
Output: [1, 2, 8, 3, 5]
Por quê: 3 troca de lugar com o seu filho 1, depois 5 desce da raiz passando por 1 e 2
Input: nums = [9, 8, 7, 6, 5, 4, 3, 2, 1]
Output: [1, 2, 3, 6, 5, 4, 7, 8, 9]
Input: nums = [42]
Output: [42]
Por quê: edge case: um único elemento já é um heap
Dicas
0 / 3
As folhas já são heaps de tamanho um, então não há nada a fazer na segunda metade da lista. O último índice com filho é n // 2 - 1.
O sift down conserta um pai cujas duas subárvores já são heaps: troque-o com o menor filho enquanto esse filho for menor que ele, e siga-o para baixo.
Chame o sift down para i de n // 2 - 1 até 0. Ir de trás para frente garante que as duas subárvores de i foram consertadas antes de i.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Solução
O heapify bottom-up trata a lista como uma árvore e a conserta a partir dos pais mais baixos, subindo. O sift down só funciona quando as duas subárvores de um nó já são heaps, e processar os índices de n // 2 - 1 até 0 garante isso, porque todo filho tem índice maior e foi tratado antes. Cada sift down troca o nó com o seu menor filho até que nenhum filho seja menor, o que restaura a ordem de heap naquela subárvore. Inserir os valores um a um custaria O(n log n), mas aqui a maioria dos nós fica perto da base e só pode descer um ou dois níveis: o trabalho total soma O(n). O espaço é O(1), porque tudo acontece dentro da lista.
def sift_down(a, i, n):
while True:
smallest, left, right = i, 2 * i + 1, 2 * i + 2
if left < n and a[left] < a[smallest]:
smallest = left
if right < n and a[right] < a[smallest]:
smallest = right
if smallest == i: # both children are larger: done
return
a[i], a[smallest] = a[smallest], a[i]
i = smallest # follow the value down
def heapify(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1): # last parent back to the root
sift_down(a, i, n)
return a
print(heapify([5, 3, 8, 1, 2])) # -> [1, 2, 8, 3, 5]
print(heapify([9, 8, 7, 6, 5, 4, 3, 2, 1])) # -> [1, 2, 3, 6, 5, 4, 7, 8, 9]
print(heapify([42])) # -> [42]Travou na ideia, e não no código? Heapify e sift explica isso.