Montículo (estructura de datos)

En informática , un montón es una estructura de datos basada en árboles que satisface la propiedad de montón : En un montón máximo , para cualquier nodo C dado, si P es el nodo padre de C, entonces la clave (el valor ) de P es mayor o igual que la clave de C. En un montón mínimo , la clave de P es menor o igual que la clave de C. ^{[ 1 ]} El nodo en la "cima" del montón (sin padres) se llama nodo raíz .

El montículo es una implementación de máxima eficiencia de un tipo de dato abstracto llamado cola de prioridad . De hecho, las colas de prioridad suelen denominarse "montículos", independientemente de su implementación. En un montículo, el elemento de mayor (o menor) prioridad siempre se almacena en la raíz. Sin embargo, un montículo no es una estructura ordenada; puede considerarse parcialmente ordenada. Un montículo es una estructura de datos útil cuando es necesario eliminar repetidamente el objeto con la mayor (o menor) prioridad, o cuando las inserciones deben intercalarse con eliminaciones del nodo raíz.

Una implementación común de un montón es el montón binario , en el que el árbol es un árbol binario completo ^{[ 2 ]} (ver figura). La estructura de datos de montón, específicamente el montón binario, fue introducida por JWJ Williams en 1964, como una estructura de datos para el algoritmo de ordenación heapsort . ^{[ 3 ]} Los montones también son cruciales en varios algoritmos de grafos eficientes como el algoritmo de Dijkstra . Cuando un montón es un árbol binario completo, tiene la altura más pequeña posible: un montón con N nodos y a ramas para cada nodo siempre tiene log _a N de altura.

Cabe destacar que, como se muestra en el gráfico, no existe un orden implícito entre hermanos o primos, ni una secuencia predefinida para un recorrido en orden (como ocurriría, por ejemplo, en un árbol de búsqueda binaria ). La relación de montículo mencionada anteriormente se aplica únicamente entre los nodos y sus padres o abuelos. El número máximo de hijos que puede tener cada nodo depende del tipo de montículo.

Los montículos se construyen normalmente en el mismo array donde se almacenan los elementos, y su estructura es implícita en el patrón de acceso de las operaciones. En este sentido, los montículos se diferencian de otras estructuras de datos con límites teóricos similares o, en algunos casos, mejores, como los árboles radix, en que no requieren memoria adicional más allá de la utilizada para almacenar las claves.

Las operaciones comunes que involucran montones son:

Básico

• find-max (o find-min ): encuentra el elemento máximo de un montículo máximo o el elemento mínimo de un montículo mínimo, respectivamente (también conocido como peek ).
• insertar : agregar una nueva clave al montón (también conocido como push ^{[ 4 ]} )
• extract-max (o extract-min ): devuelve el nodo de valor máximo de un montón máximo [o valor mínimo de un montón mínimo] después de eliminarlo del montón (también conocido como pop ^{[ 5 ]} ).
• delete-max (o delete-min ): elimina el nodo raíz de un montón máximo (o mínimo), respectivamente.
• reemplazar : extraer la raíz y agregar una nueva clave. Esto es más eficiente que extraer seguida de agregar, ya que solo necesita equilibrarse una vez, no dos, y es apropiado para montones de tamaño fijo. ^{[ 6 ]}

Creación

• create-heap : crea un montón vacío
• heapify : crea un montón a partir de una matriz de elementos dada.
• fusión ( unión ): unir dos montones para formar un nuevo montón válido que contenga todos los elementos de ambos, preservando los montones originales.
• fusionar : unir dos montones para formar un nuevo montón válido que contenga todos los elementos de ambos, destruyendo los montones originales.

Inspección

• tamaño : devuelve el número de elementos en el montón.
• is-empty : devuelve verdadero si el montón está vacío, falso en caso contrario.

Interno

• increment-key o decrease-key : actualizan una clave dentro de un montón máximo o mínimo, respectivamente.
• delete : elimina un nodo arbitrario (seguido del movimiento del último nodo y el filtrado para mantener el montón).
• sift-up : mueve un nodo hacia arriba en el árbol, tanto como sea necesario; se utiliza para restaurar la condición del montón después de la inserción. Se llama "tamiz" porque el nodo se mueve hacia arriba en el árbol hasta alcanzar el nivel correcto, como en un tamiz .
• sift-down : mueve un nodo hacia abajo en el árbol, de forma similar a sift-up; se utiliza para restaurar el estado del montón después de una eliminación o reemplazo.

Los montones se suelen implementar con un array , como se muestra a continuación:

• Cada elemento del array representa un nodo del montón, y
• La relación padre/hijo se define implícitamente mediante los índices de los elementos en el array.

Para un montón binario , en el arreglo, el primer índice contiene el elemento raíz. Los siguientes dos índices del arreglo contienen los hijos de la raíz. Los siguientes cuatro índices contienen los cuatro hijos de los dos nodos hijos de la raíz, y así sucesivamente. Por lo tanto, dado un nodo en el índice i , sus hijos están en los índices${\displaystyle 2i+1}$y​​${\displaystyle 2i+2}$⁠ , y su padre está en el índice ⌊( i −1)/2⌋ en una matriz que comienza desde el índice ⁠${\displaystyle 0}$⁠ , o en ⁠${\displaystyle 2i}$,​​${\displaystyle 2i+1}$⁠ , y ⌊ i /2⌋ , respectivamente, en una matriz que comienza desde ⁠${\displaystyle 1}$Este sencillo esquema de indexación permite recorrer el árbol de forma eficiente, tanto hacia arriba como hacia abajo.

El equilibrio de un montón se logra mediante operaciones de intercambio (intercambio de elementos que están fuera de orden). Dado que podemos construir un montón a partir de un arreglo sin necesidad de memoria adicional (para los nodos, por ejemplo), el algoritmo de ordenación por montículos (heapsort ) se puede utilizar para ordenar un arreglo in situ.

Después de insertar o eliminar un elemento de un montón, la propiedad del montón puede verse comprometida y este debe reequilibrarse intercambiando elementos dentro del array.

Aunque los distintos tipos de montículos implementan las operaciones de manera diferente, la forma más común es la siguiente:

• Inserción: Añada el nuevo elemento al final del montón, en el primer espacio libre disponible. Si esto infringe la propiedad del montón, mueva el nuevo elemento hacia arriba ( operación de natación ) hasta que se restablezca dicha propiedad.
• Extracción: Elimine la raíz e inserte el último elemento del montón en la raíz. Si esto infringe la propiedad del montón, procese la nueva raíz ( operación de sumidero ) para restablecer dicha propiedad.
• Reemplazo: Elimine la raíz, coloque el nuevo elemento en la raíz y proceda a filtrar hacia abajo. En comparación con la extracción seguida de la inserción, esto evita un paso de filtrado hacia arriba.

La construcción de un montón binario (o d -ario) a partir de un arreglo dado de elementos se puede realizar en tiempo lineal utilizando el algoritmo clásico de Floyd , con un número de comparaciones en el peor de los casos igual a 2 N − 2 s ₂ ( N ) − e ₂ ( N ) (para un montón binario), donde s ₂ ( N ) es la suma de todos los dígitos de la representación binaria de N y e ₂ ( N ) es el exponente de 2 en la factorización prima de N . ^{[ 7 ]} Esto es más rápido que una secuencia de inserciones consecutivas en un montón originalmente vacío, que es logarítmicamente lineal. ^{[ a ]}

Aquí se muestran las complejidades temporales ^{[ 8 ]} de diversas estructuras de datos de montículo. La abreviatura am. indica que la complejidad dada está amortizada; de lo contrario, se trata de la complejidad en el peor de los casos. Para conocer el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones presuponen un montículo máximo.

La estructura de datos de montón tiene muchas aplicaciones.

• Heapsort : Uno de los mejores métodos de ordenación, ya que se realiza in situ y no presenta escenarios cuadráticos en el peor de los casos.
• Algoritmos de selección : Un montículo permite acceder al elemento mínimo o máximo en tiempo constante, y otras selecciones (como la mediana o el k-ésimo elemento) se pueden realizar en tiempo sublineal sobre datos que se encuentran en un montículo. ^{[ 24 ]}
• Algoritmos de grafos : Al usar montículos como estructuras de datos internas para el recorrido, el tiempo de ejecución se reduce en orden polinomial. Ejemplos de estos problemas son el algoritmo de árbol de expansión mínima de Prim y el algoritmo de camino más corto de Dijkstra .
• Cola de prioridad : Una cola de prioridad es un concepto abstracto como "una lista" o "un mapa"; al igual que una lista se puede implementar con una lista enlazada o un arreglo, una cola de prioridad se puede implementar con un montón o con una variedad de otros métodos.
• Fusión de K vías : Una estructura de datos de montón es útil para fusionar múltiples flujos de entrada ya ordenados en un único flujo de salida ordenado. Ejemplos de la necesidad de fusión incluyen la ordenación externa y la transmisión de resultados de datos distribuidos, como un árbol de fusión estructurado en registro. El bucle interno obtiene el elemento mínimo, lo reemplaza con el siguiente elemento del flujo de entrada correspondiente y luego realiza una operación de reducción de montón. (Alternativamente, se puede usar la función de reemplazo). (El uso de las funciones de extracción del máximo e inserción de una cola de prioridad es mucho menos eficiente).

• La biblioteca estándar de C++ proporciona los algoritmos `make_heap` , `push_heap` y `pop_heap` para montículos (generalmente implementados como montículos binarios), que operan sobre iteradores de acceso aleatorio arbitrarios . Trata los iteradores como referencias a un array y utiliza la conversión de array a montículo. También proporciona la clase `std::priority_queue` , que encapsula estas funcionalidades en una clase tipo contenedor. Sin embargo, no existe soporte estándar para las operaciones de reemplazo, desplazamiento ascendente/descendente ni disminución/incremento de claves.
• Las bibliotecas Boost C++ incluyen una biblioteca de montículos ^{[ 25 ]} . A diferencia de la STL, admite operaciones de disminución e incremento, y admite tipos adicionales de montículos: específicamente, admite montículos d- arios, binomiales, de Fibonacci, de emparejamiento y sesgados.
• Existe una implementación genérica de montón para C y C++ con soporte para montones D y B. Proporciona una API similar a la de la STL.
• La biblioteca estándar del lenguaje de programación D incluye std.container.BinaryHeap , que se implementa en términos de rangos de D. Se pueden construir instancias a partir de cualquier rango de acceso aleatorio . BinaryHeap expone una interfaz de rango de entrada que permite la iteración con las sentencias foreach integradas de D y la integración con la API basada en rangos del paquete std.algorithm .
• Para Haskell existe el módulo Data.Heap .
• La plataforma Java (desde la versión 1.5) proporciona una implementación de montón binario con la clase java.util.PriorityQueuedel Java Collections Framework . Esta clase implementa por defecto un montón mínimo; para implementar un montón máximo, el programador debe escribir un comparador personalizado. No se admiten las operaciones de reemplazo, desplazamiento ascendente/descendente ni disminución/incremento de claves.
• Python cuenta con un módulo heapq que implementa una cola de prioridad utilizando un montón binario. La biblioteca expone una función heapreplace para admitir la fusión de k vías.
• PHP cuenta con memoria máxima ( SplMaxHeap ) y memoria mínima ( SplMinHeap ) desde la versión 5.3 en la biblioteca estándar de PHP.
• Perl cuenta con implementaciones de montículos binarios, binomiales y de Fibonacci en la distribución Heap disponible en CPAN .
• El lenguaje Go incluye un paquete `heap` con algoritmos que operan sobre un tipo arbitrario que satisface una interfaz determinada. Este paquete no admite las operaciones de reemplazo, indexación ascendente/descendente ni de disminución/aumento de clave.
• La biblioteca Core Foundation de Apple contiene una estructura CFBinaryHeap .
• Pharo incluye una implementación de un montón en el paquete Collections-Sequenceable, junto con un conjunto de casos de prueba. El montón se utiliza en la implementación del bucle de eventos del temporizador.
• El lenguaje de programación Rust cuenta con una implementación de montículo máximo binario, BinaryHeap , en el módulo collections de su biblioteca estándar.
• .NET cuenta con la clase PriorityQueue , que utiliza una implementación de min-heap cuaternaria (d-aria). Está disponible a partir de .NET 6.

• Algoritmo de ordenación
• Estructura de datos de búsqueda
• Treap , una forma de árbol de búsqueda binaria basada en árboles ordenados por montículo.

• Montón en Wolfram MathWorld
• Explicación de cómo funcionan los algoritmos básicos de montículo.
• Bentley, Jon Louis (2000). Perlas de programación (2.ª  ed.). Addison Wesley. págs. 147–162 . ISBN  0201657880.