Verificar se o array é um min-heap
A missão
Problema
Uma lista de números pode ser lida como uma árvore binária: o valor no índice i tem os seus filhos nos índices 2i + 1 e 2i + 2, quando eles existem. Decida se a lista já satisfaz a regra do min-heap, ou seja, se nenhum valor é maior que algum dos seus filhos. Retorne True se satisfizer e False caso contrário. Uma lista vazia ou com um único valor conta como um heap válido.
Exemplos
Input: values = [1, 3, 2, 7, 4]
Output: True
Por quê: 1 fica acima de 3 e 2, e 3 fica acima de 7 e 4
Input: values = [2, 1, 3]
Output: False
Por quê: a raiz 2 é maior que o seu filho esquerdo 1
Input: values = [5, 5, 5]
Output: True
Por quê: edge case: valores iguais nunca quebram a regra
Dicas
0 / 3
Você nunca precisa construir uma árvore. A aritmética dos índices já diz quem é pai de quem.
Se nenhum pai for maior que os seus próprios filhos, a regra vale até o fim, porque “menor ou igual” se encadeia.
Percorra cada índice de 1 até o fim, encontre o pai dele em (i - 1) // 2 e falhe assim que um pai for maior que o filho. Se o percurso terminar, a lista é um heap.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- the list may be empty
Solução
A regra do heap é local: se nenhum pai for maior que os seus filhos, então todo ancestral é menor ou igual a todos os seus descendentes, porque as comparações se encadeiam. Por isso basta comparar cada índice que não é a raiz com o seu pai, que fica em (i - 1) // 2. Verificar pelo lado do filho visita cada par pai-filho exatamente uma vez. O tempo é O(n) e o espaço é O(1).
def is_min_heap(values):
for child in range(1, len(values)):
parent = (child - 1) // 2 # the array position of this value's parent
if values[parent] > values[child]:
return False # one broken pair is enough to fail
return True
print(is_min_heap([1, 3, 2, 7, 4])) # -> True
print(is_min_heap([2, 1, 3])) # -> False
print(is_min_heap([5, 5, 5])) # -> TrueTravou na ideia, e não no código? Heapify e sift explica isso.