Comprobar si un array es un min-heap
La misión
Problema
Una lista de números puede leerse como un árbol binario: el valor en el índice i tiene sus hijos en los índices 2i + 1 y 2i + 2, cuando existen. Decide si la lista ya cumple la regla del min-heap, es decir, que ningún valor sea mayor que alguno de sus hijos. Devuelve True si la cumple y False en caso contrario. Una lista vacía o con un solo valor cuenta como un heap (montículo) válido.
Ejemplos
Input: values = [1, 3, 2, 7, 4]
Output: True
Por qué: 1 está encima de 3 y 2, y 3 está encima de 7 y 4
Input: values = [2, 1, 3]
Output: False
Por qué: la raíz 2 es mayor que su hijo izquierdo 1
Input: values = [5, 5, 5]
Output: True
Por qué: caso límite: los valores iguales nunca rompen la regla
Pistas
0 / 3
Nunca necesitas construir un árbol. La aritmética de índices ya te dice quién es el padre de quién.
Si ningún padre es mayor que sus propios hijos, la regla se cumple hasta el fondo, porque “menor o igual” se encadena.
Recorre cada índice desde 1 hasta el final, encuentra su padre en (i - 1) // 2 y falla en cuanto un padre sea mayor que el hijo. Si el recorrido termina, la lista es un heap.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- the list may be empty
Solución
La regla del heap es local: si ningún padre es mayor que sus hijos, entonces ningún ancestro es mayor que ningún descendiente, porque las comparaciones se encadenan. Por eso basta con comparar cada índice que no sea la raíz con su padre, que está en (i - 1) // 2. Comparar desde el lado del hijo visita cada par padre-hijo exactamente una vez. El tiempo es O(n) y el espacio es 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])) # -> True¿Lo que te frena es la idea y no el código? Heapify y sift lo explica.