Pular para o conteúdo

Heapify in-place de uma lista

Fácil#heapify#sift-down~15 min

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

Tempo-alvo
O(n)
Espaço-alvo
O(1)

Travou na ideia, e não no código? Heapify e sift explica isso.

Python 3Ctrl+Enter executa