¿Qué es una pila?

Un montón (heap) es una estructura de datos en forma de árbol especial que cumple con la propiedad de montón. Esta propiedad indica que para cualquier vértice, excepto la raíz, el valor de la clave de ese vértice debe estar en cierta relación con el valor de la clave de su padre. Hay dos tipos principales de montones:

• Montón máximo (Max-heap): El valor de la clave de cada vértice no es menor que el valor de las claves de sus hijos. El elemento máximo está en la raíz.
• Montón mínimo (Min-heap): El valor de la clave de cada vértice no es mayor que el valor de las claves de sus hijos. El elemento mínimo está en la raíz.

El montón generalmente se implementa como un array, lo que permite acceder a los elementos de manera eficiente y realizar operaciones. La relación entre padres e hijos en el array es la siguiente:

• Para un elemento con índice i (comenzando desde 0), su hijo izquierdo está en el índice 2i + 1.
• Su hijo derecho está en el índice 2i + 2.
• Su padre está en el índice floor((i - 1) / 2).

Operaciones principales en un montón:

• Insertar: Añadir un nuevo elemento. Tiempo de ejecución O(log n), donde n es el número de elementos.
• Extraer Máximo / Extraer Mínimo: Eliminar y devolver el elemento máximo (en un montón máximo) o mínimo (en un montón mínimo). Tiempo de ejecución O(log n).
• Heapify (Construcción del montón): Transformar un array arbitrario en un montón. Tiempo de ejecución O(n).

Los montones se utilizan en algoritmos de ordenamiento (por ejemplo, ordenamiento por montículo), en colas de prioridad, y en algoritmos de búsqueda de caminos más cortos (por ejemplo, el algoritmo de Dijkstra).