Un heap (montículo) es una estructura de datos de tipo árbol especializada que cumple la siguiente propiedad:
🗼
Si P es el nodo padre de C, entonces el valor de P es mayor o igual (en un max-heap) o menor o igual (en un min-heap) que el valor de C.
Un ejemplo de max-heap con 8 nodos
Existen dos tipos principales de heaps:
Max Heap: El valor del nodo padre debe ser mayor o igual que el de sus nodos hijos.
Min Heap: El valor del nodo padre debe ser menor o igual que el de sus nodos hijos.
Nos centraremos en el max-heap, ya que la mayoría de las bibliotecas estándar implementan un max-heap para colas de prioridad. En un max-heap, la raíz del árbol es el elemento más grande, mientras que las hojas son las más pequeñas. Sin embargo, no hay un orden específico para las hojas. Lo único que se garantiza es que el nodo raíz sea el más grande y que sus nodos hijos sean menores o iguales a su valor.
Ten en cuenta que la última fila del heap siempre se llena de izquierda a derecha. Es decir, primero se llena la hoja más a la izquierda y, por último, la hoja más a la derecha, como se muestra en la figura anterior.
Implementación
Un heap (montículo) se puede implementar como un arreglo, en donde el primer elemento del arreglo representa el nodo raíz. Dado que cada nodo tiene solo dos nodos hijos, podemos organizar los índices así:
El elemento raíz se ubica en el índice 1.
Los hijos izquierdo y derecho de un nodo se encuentran en los índices 2i y 2i+1, respectivamente.
El nodo padre de un elemento que está en el índice i se ubica en el índice i // 2.
El heap de arriba se puede representar en una lista así:
# Solo lee cada fila en la figura y coloca los números uno al lado del otro
heap = [None, 8, 5, 7, 1, 1, 6, 3, 1]
# O para visualizarlo mejor
heap = [None, # Saltamos el índice [0] para simplificar el manejo de índices
8, # Índice [1]
5, 7, # Índices [2, 3]
1, 1, 6, 3, # Índices [4, 5, 6, 7]
1] # Índice [8]
Desafío: verificar si el árbol binario es un heap
Dado un árbol binario representado por un arreglo de n números (con la misma indexación descrita arriba), se te pide comprobar si cumple las propiedades de un max-heap.
Entrada
La primera línea de la entrada contiene un único número entero n (1 ≤ n ≤ 100 000).
La siguiente línea contiene n enteros separados por un espacio, () que representan los valores de los elementos en el heap.
Salida
El programa debe imprimir Yes si el árbol binario de la entrada cumple la propiedad de max-heap, o No en caso contrario.
Ejemplos
Entrada
Salida
8
8 5 7 1 1 6 3 1
Yes
7
8 5 7 1 9 6 3
No
Explicación
Ejemplo 1
All the parent nodes have a value larger than or equal to their child nodes. Therefore, the heap property is satisfied.
Ejemplo 2
The node with a value of 9 is larger than its parent node. Therefore, the heap property is not satisfied.
