Saltar al contenido

Comprobar si un array es un min-heap

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

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

Tiempo objetivo
O(n)
Espacio objetivo
O(1)

Restricciones

  • the list may be empty

¿Lo que te frena es la idea y no el código? Heapify y sift lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio