Pular para o conteúdo

Verificar se o array é um min-heap

Fácil#heap#array-as-tree~15 min

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

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

Restrições

  • the list may be empty

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

Python 3Ctrl+Enter executa
Caso de teste personalizado