¿Qué es una pila (en el contexto de estructuras de datos)?

Un montón (heap) es un árbol especializado que se utiliza como estructura de datos. La propiedad principal del montón es el orden parcial: para cualquier vértice, se cumple la condición de que el valor del vértice padre es mayor o igual que el valor de cualquiera de sus hijos (max-heap) o menor o igual (min-heap).

Características clave:

• Árbol binario: Se implementa generalmente como un árbol binario, donde cada nodo tiene como máximo dos hijos.
• Árbol binario completo: En todos los niveles, excepto posiblemente el último, el árbol está completamente lleno. Los nodos en el último nivel se llenan de izquierda a derecha. Esto permite almacenar eficientemente el montón en forma de array.
• Propiedad del montón:
  • Max-heap: El valor de cada nodo es mayor o igual que los valores de sus hijos. El elemento máximo siempre está en la raíz.
  • Min-heap: El valor de cada nodo es menor o igual que los valores de sus hijos. El elemento mínimo siempre está en la raíz.

Operaciones principales con el montón:

• Inserción de un elemento: Añadir un nuevo elemento y mantener la propiedad del montón.
• Eliminación de un elemento: Eliminar el elemento raíz (el máximo o mínimo, dependiendo del tipo de montón) y mantener la propiedad del montón.
• Construcción del montón: Construir un montón a partir de un array de elementos.

Aplicaciones del montón:

• Ordenamiento: Algoritmo de ordenamiento por montículo (Heapsort).
• Colas de prioridad: Implementación eficiente de colas donde los elementos se procesan en orden de prioridad.
• Algoritmos de búsqueda: Por ejemplo, búsqueda del elemento k-ésimo en orden de magnitud.
• Algoritmos en grafos: Por ejemplo, el algoritmo de Dijkstra.

Representación del montón en array:

Dado que el montón es un árbol binario completo, puede almacenarse eficientemente en un array sin usar punteros.

• Si un nodo está en el índice i, su hijo izquierdo está en el índice 2*i + 1.
• Su hijo derecho está en el índice 2*i + 2.
• Su padre está en el índice (i - 1) / 2.

# Ejemplo de representación de un min-heap en forma de array
heap_array = [10, 15, 20, 17, 25, 30]

# Raíz: heap_array[0] = 10
# Hijo izquierdo de la raíz: heap_array[2*0 + 1] = heap_array[1] = 15
# Hijo derecho de la raíz: heap_array[2*0 + 2] = heap_array[2] = 20
# Padre del elemento en el índice 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15