Montón (estructura de datos)

Estructura de datos de informática

Ejemplo de un montón máximo binario con claves de nodo que son números enteros entre 1 y 100

En informática , un montón es una estructura de datos basada en árboles que satisface la propiedad del montón : en un montón máximo , para cualquier nodo C dado, si P es un 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 "parte superior" del montón (sin padres) se denomina nodo raíz .

El montón es una implementación de máxima eficiencia de un tipo de datos abstracto llamado cola de prioridad y, de hecho, las colas de prioridad a menudo se denominan "montones", independientemente de cómo se implementen. En un montón, el elemento de mayor (o menor) prioridad siempre se almacena en la raíz. Sin embargo, un montón no es una estructura ordenada; se puede considerar que está parcialmente ordenada. Un montón 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 del montón, específicamente el montón binario, fue introducida por} JWJ Williams en 1964, como una estructura de datos para el algoritmo de ordenamiento 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 una rama para cada nodo siempre tiene una altura de log _a N.

Tenga en cuenta que, como se muestra en el gráfico, no hay un orden implícito entre hermanos o primos ni una secuencia implícita para un recorrido en orden (como habría, por ejemplo, en un árbol de búsqueda binario ). La relación de montón mencionada anteriormente se aplica solo entre nodos y sus padres, abuelos. La cantidad máxima de hijos que puede tener cada nodo depende del tipo de montón.

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

Operaciones

Las operaciones comunes que involucran montones son:

Básico

• find-max (o find-min ): busca un elemento máximo de un montón máximo, o un elemento mínimo de un montón 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 ): eliminar el nodo raíz de un montón máximo (o montón mínimo), respectivamente
• replace : extraer la raíz y enviar una nueva clave. Esto es más eficiente que extraer la raíz y enviarla, ya que solo necesita equilibrarse una vez, no dos, y es adecuado 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 dada de elementos
• fusionar ( 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

• aumentar-clave o disminuir-clave : actualizar una clave dentro de un montón máximo o mínimo, respectivamente
• eliminar : elimina un nodo arbitrario (seguido de mover el último nodo y filtrar para mantener el montón)
• tamizar : mover 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 denomina "tamizar" porque el nodo se mueve hacia arriba en el árbol hasta que alcanza el nivel correcto, como en un tamiz .
• sift-down : mover un nodo hacia abajo en el árbol, similar a sift-up; se utiliza para restaurar la condición del montón después de una eliminación o reemplazo.

Implementación

Los montones generalmente se implementan con una matriz , de la siguiente manera:

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

Ejemplo de un montón máximo binario completo con claves de nodo que son números enteros del 1 al 100 y cómo se almacenarían en una matriz.

En un montón binario , en la matriz, el primer índice contiene el elemento raíz. Los dos índices siguientes de la matriz contienen los hijos de la raíz. Los cuatro índices siguientes 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⌋ . Este sencillo esquema de indexación hace que sea eficiente moverse "hacia arriba" o "hacia abajo" en el árbol.

El equilibrio de un montón se realiza mediante operaciones de tamizado hacia arriba o hacia abajo (intercambio de elementos que están fuera de orden). Como podemos crear un montón a partir de una matriz sin necesidad de memoria adicional (para los nodos, por ejemplo), se puede utilizar heapsort para ordenar una matriz en el lugar.

Después de insertar o eliminar un elemento de un montón, es posible que se viole la propiedad del montón y se debe volver a equilibrar el montón intercambiando elementos dentro de la matriz.

Aunque los diferentes tipos de montones implementan las operaciones de manera diferente, la forma más común es la siguiente:

• Inserción: agregar el nuevo elemento al final del montón, en el primer espacio libre disponible. Si esto viola la propiedad del montón, filtrar el nuevo elemento ( operación de nado ) hasta que se restablezca la propiedad del montón.
• Extracción: elimine la raíz e inserte el último elemento del montón en la raíz. Si esto viola la propiedad del montón, filtre la nueva raíz ( operación de sumidero ) para restablecer la propiedad del montón.
• Reemplazo: retire la raíz y coloque el nuevo elemento en la raíz y tamice hacia abajo. En comparación con la extracción seguida de la inserción, esto evita un paso de tamizado hacia arriba.

La construcción de un montón binario (o d -ario) a partir de una matriz dada de elementos se puede realizar en tiempo lineal utilizando el algoritmo clásico de Floyd , con el 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 log-lineal. ^[a]

Variantes

• 2–3 montón
• Montón B
• pitido
• Montón binario
• Montón binomial
• Cola de Brodal
• montón d -ario
• Montón de Fibonacci
• Montón de KD
• Montón de hojas
• Montón de izquierdistas
• Montón binomial sesgado
• Montón de Fibonacci estricto
• Montón mínimo-máximo
• Montón de emparejamiento
• Montón de radix
• Montón fusionable aleatorio
• Montón sesgado
• Montón blando
• Montón ternario
• Tratar
• Montón débil

Comparación de límites teóricos para variantes

Aquí se muestran las complejidades temporales ^[8] de varias estructuras de datos de heap. La abreviatura am. indica que la complejidad dada se amortiza, de lo contrario es una complejidad del peor caso. Para el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones suponen un heap máximo.

1. Cada inserción ocupa O(log( k )) en el tamaño existente del montón, por lo tanto . Dado que , un factor constante (la mitad) de estas inserciones están dentro de un factor constante del máximo, por lo que asintóticamente podemos suponer ; formalmente el tiempo es . Esto también se puede ver fácilmente a partir de la aproximación de Stirling . ${\displaystyle \sum _{k=1}^{n}O(\log k)}$ ${\displaystyle \log n/2=(\log n)-1}$ ${\displaystyle k=n}$ ${\displaystyle nO(\log n)-O(n)=O(n\log n)}$
2. make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar en Θ ( n ) tiempo siempre que meld se ejecute en O (log  n ) tiempo (donde ambas complejidades se pueden amortizar). ^{[9] [10]} Otro algoritmo logra Θ ( n ) para montones binarios. ^[11]
3. Para los montículos persistentes (que no admiten increase-key ), una transformación genérica reduce el costo de meld al de insert , mientras que el nuevo costo de delete-max es la suma de los costos anteriores de delete-max y meld . ^[14] Aquí, hace que meld se ejecute en Θ (1) tiempo (amortizado, si el costo de insert es) mientras que delete-max todavía se ejecuta en O (log  n ). Aplicado a montículos binomiales sesgados, produce colas Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos. ^[13]
4. Límite inferior de ^[17] límite superior de ^[18] ${\displaystyle \Omega (\log \log n),}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$
5. colas de Brodal y los montículos de Fibonacci estrictos logran complejidades óptimas en el peor de los casos para los montículos. Primero se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que logra el mismo óptimo, excepto que no se admite la clave de incremento .

Aplicaciones

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

• Heapsort : uno de los mejores métodos de ordenamiento implementado y sin escenarios cuadráticos de peor caso.
• Algoritmos de selección : un montón permite el acceso al elemento mínimo o máximo en tiempo constante, y otras selecciones (como la mediana o el elemento k) se pueden realizar en tiempo sublineal en datos que están en un montón. ^[24]
• Algoritmos de gráficos : al utilizar montículos como estructuras de datos de recorrido interno, el tiempo de ejecución se reducirá en orden polinomial. Algunos ejemplos de estos problemas son el algoritmo de árbol de expansión mínima de Prim y el algoritmo de ruta más corta de Dijkstra .
• Cola de prioridad : una cola de prioridad es un concepto abstracto como "una lista" o "un mapa"; así como una lista se puede implementar con una lista enlazada o una matriz, una cola de prioridad se puede implementar con un montón o una variedad de otros métodos.
• Fusión de K-way : una estructura de datos de montón es útil para fusionar muchos flujos de entrada ya ordenados en un único flujo de salida ordenado. Algunos 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 con estructura de registro. El bucle interno obtiene el elemento mínimo, lo reemplaza con el siguiente elemento para el flujo de entrada correspondiente y luego realiza una operación de tamizado de montón. (Alternativamente, la función de reemplazo). (El uso de las funciones extract-max e insert de una cola de prioridad es mucho menos eficiente).

Implementaciones de lenguajes de programación

• 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 en iteradores de acceso aleatorio arbitrarios . Trata a los iteradores como una referencia a una matriz y utiliza la conversión de matriz a montículo. También proporciona el adaptador de contenedor priority_queue , que envuelve estas funciones en una clase similar a un contenedor. Sin embargo, no hay soporte estándar para las operaciones replace, sift-up/sift-down o decrease/increase-key.
• Las bibliotecas Boost C++ incluyen una biblioteca de montículos. A diferencia de STL, admite operaciones de aumento y disminución, 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 de montón genérica para C y C++ con soporte para montón D-ario y montón B. Proporciona una API similar a STL.
• La biblioteca estándar del lenguaje de programación D incluye std.container.BinaryHeap, que se implementa en términos de los rangos de D. Las instancias se pueden construir a partir de cualquier rango de acceso aleatorio. BinaryHeap expone una interfaz de rango de entrada que permite la iteración con las instrucciones 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.PriorityQueueen Java Collections Framework . Esta clase implementa de forma predeterminada un montón mínimo; para implementar un montón máximo, el programador debe escribir un comparador personalizado. No hay soporte para las operaciones de reemplazo, selección ascendente/descendente o disminución/aumento de clave.
• Python tiene 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-way.
• PHP tiene tanto max-heap ( SplMaxHeap ) como min-heap ( SplMinHeap ) a partir de la versión 5.3 en la biblioteca PHP estándar.
• Perl tiene implementaciones de montículos binarios, binomiales y de Fibonacci en la distribución Heap disponible en CPAN .
• El lenguaje Go contiene un paquete de montón con algoritmos de montón que operan sobre un tipo arbitrario que satisface una interfaz determinada. Ese paquete no admite las operaciones de reemplazo, tamizado hacia arriba/abajo o disminución/aumento de clave.
• La biblioteca Core Foundation de Apple contiene una estructura CFBinaryHeap.
• Pharo tiene una implementación de un montón en el paquete Collections-Sequenceable junto con un conjunto de casos de prueba. Un montón se utiliza en la implementación del bucle de eventos del temporizador.
• El lenguaje de programación Rust tiene una implementación de montón máximo binario, BinaryHeap, en el módulo de colecciones de su biblioteca estándar.
• .NET tiene la clase PriorityQueue, que utiliza una implementación de min-heap cuaternaria (d-aria). Está disponible a partir de .NET 6.

Véase también

• Algoritmo de ordenación
• Estructura de datos de búsqueda
• Pila (tipo de datos abstracto)
• Cola (tipo de datos abstracto)
• Árbol (estructura de datos)
• Treap , una forma de árbol de búsqueda binaria basado en árboles ordenados por montón

Referencias

1. Black (ed.), Paul E. (14 de diciembre de 2004). Entrada para heap en Dictionary of Algorithms and Data Structures . Versión en línea. Instituto Nacional de Estándares y Tecnología de EE. UU ., 14 de diciembre de 2004. Recuperado el 8 de octubre de 2017 de https://xlinux.nist.gov/dads/HTML/heap.html.
2. CORMEN, THOMAS H. (2009). INTRODUCCIÓN A LOS ALGORITMOS . Estados Unidos de América: The MIT Press Cambridge, Massachusetts Londres, Inglaterra. pp. 151–152. ISBN 978-0-262-03384-8.
3. Williams, JWJ (1964), "Algoritmo 232 - Heapsort", Comunicaciones de la ACM , 7 (6): 347–348, doi :10.1145/512274.512284
4. La biblioteca estándar de Python, 8.4. heapq — Algoritmo de cola de montón, heapq.heappush
5. La biblioteca estándar de Python, 8.4. heapq — Algoritmo de cola de montón, heapq.heappop
6. La biblioteca estándar de Python, 8.4. heapq — Algoritmo de cola de montón, heapq.heapreplace
7. Suchenek, Marek A. (2012), "Análisis elemental pero preciso del peor de los casos del programa de construcción de pilas de Floyd", Fundamenta Informaticae , 120 (1), IOS Press: 75–92, doi :10.3233/FI-2012-751.
8. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.
9. Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montones autoajustables". Revista SIAM de informática . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN  0097-5397. 
10. Tarjan, Robert (1983). "3.3. Montones de izquierdas". Estructuras de datos y algoritmos de red . págs. 38-42. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
11. Hayward, Ryan; McDiarmid, Colin (1991). "Análisis de caso promedio de construcción de montículos mediante inserción repetida" (PDF) . J. Algorithms . 12 : 126–153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Archivado desde el original (PDF) el 2016-02-05 . Consultado el 2016-01-28 . 
12. "Pila binomial | Wiki de matemáticas y ciencias brillante". brilliant.org . Consultado el 30 de septiembre de 2019 .
13. Brodal, Gerth Stølting; Okasaki, Chris (noviembre de 1996), "Colas de prioridad puramente funcionales óptimas", Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
14. Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). pp. 158-162. ISBN 9780521631242.
15. Takaoka, Tadao (1999), Teoría de 2-3 montones (PDF) , pág. 12
16. Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Apuntes de clase en informática, vol. 1851, Springer-Verlag, págs. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi :10.1007/3-540-44985-X_5, ISBN  3-540-67690-2
17. Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de emparejar montones y estructuras de datos relacionadas" (PDF) . Revista de la Asociación de Maquinaria Computacional . 46 (4): 473–501. doi :10.1145/320211.320214.
18. Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF) . FOCS '05 Actas del 46.º Simposio anual IEEE sobre fundamentos de la informática. pp. 174–183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN .  0-7695-2468-0.
19. Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Informática . 40 (6): 1463–1485. doi :10.1137/100785351.
20. Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Revista de la Asociación de Maquinaria Computacional . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874. 
21. Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones de Fibonacci estrictos (PDF) . Actas del 44.º simposio sobre teoría de la computación - STOC '12. págs. 1177–1184. CiteSeerX 10.1.1.233.1740 . doi :10.1145/2213977.2214082. ISBN  978-1-4503-1245-5.
22. Brodal, Gerth S. (1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Actas del 7.º Simposio anual ACM-SIAM sobre algoritmos discretos , págs. 52-58
23. Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montículos ascendentes". Estructuras de datos y algoritmos en Java (3.ª ed.). págs. 338–341. ISBN 0-471-46983-1.
24. Frederickson, Greg N. (1993), "Un algoritmo óptimo para la selección en un min-heap", Información y computación (PDF) , vol. 104, Academic Press, págs. 197–214, doi : 10.1006/inco.1993.1030 , archivado desde el original (PDF) el 2012-12-03 , consultado el 2010-10-31

Enlaces externos

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