Montón (estructura de datos)

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 árbol 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. que o igual a la clave de C. En un montón mínimo , la clave de P es menor o igual a la clave de C. ^[1] El nodo en la "parte superior" del montón (sin padres) se llama 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 ordenado. Un montón es una estructura de datos útil cuando es necesario eliminar repetidamente el objeto con la prioridad más alta (o más baja), 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 clasificación del montón . ^[3] Los montones también son cruciales en varios algoritmos de gráficos 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 ramas para cada nodo siempre tiene _una altura de registro N.

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

Los montones generalmente se construyen in situ en la misma matriz donde se almacenan los elementos, y su estructura está implícita en el patrón de acceso de las operaciones. Los montones se diferencian de esta manera 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.

Operaciones

Las operaciones comunes que involucran montones son:

Básico

find-max (o find-min ): encuentra 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 presionar ^[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] )
eliminar-max (o eliminar-min ): eliminar el nodo raíz de un montón máximo (o montón mínimo), respectivamente
reemplazar : pop root y presione una nueva tecla. Esto es más eficiente que un pop seguido de un empujón, 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 dada de elementos
fusionar ( unión ): unir dos montones para formar un nuevo montón válido que contenga todos los elementos de ambos, conservando 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 la cantidad de elementos en el montón.
está vacío : devuelve verdadero si el montón está vacío, falso en caso contrario.

Interno

clave de aumento o clave de disminución : actualización de 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 tamizar para mantener el montón)
tamizar : mueve un nodo hacia arriba en el árbol, tanto tiempo como sea necesario; se utiliza para restaurar la condición del montón después de la inserción. Se llama "tamizar" porque el nodo sube por el árbol hasta alcanzar el nivel correcto, como en un tamiz .
tamizar hacia abajo : mueve un nodo hacia abajo en el árbol, similar a tamizar hacia arriba; se utiliza para restaurar la condición del montón después de la 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 está definida 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ía en una matriz.

Para 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 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 y , y su padre está en el índice $⌊($ $i$ $-1)/2⌋$ . Este sencillo esquema de indexación hace que sea eficaz moverse "hacia arriba" o "hacia abajo" en el árbol. $2i+1$ $2i+2$

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

Después de insertar o eliminar un elemento de un montón, se puede violar la propiedad del montón y el montón debe reequilibrarse 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: Agrega el nuevo elemento al final del montón, en el primer espacio libre disponible. Si esto viola la propiedad del montón, examine el nuevo elemento ( operación de natación ) hasta que se haya restablecido 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, examine 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. En comparación con la extracción seguida de la inserción, esto evita un paso de filtrado.

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 peor 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

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

A continuación se presentan las complejidades temporales ^[8] de varias estructuras de datos del montón. Los nombres de las funciones suponen un montón máximo. Para conocer el significado de " O ( f )" y " Θ ( f )", consulte la notación O grande .

^ Cada inserción toma 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á dentro de un factor constante del máximo, asintóticamente podemos suponer ; formalmente es el momento . Esto también puede verse fácilmente a partir de la aproximación de Stirling . $\sum _ {k=1}^{n}O(\log k)$ $\log n/2=(\log n)-1$ $k=n$ $nO(\log n)-O(n)=O(n\log n)$
^ abcdefghi Tiempo amortizado.
^ Brodal y Okasaki describen una técnica para reducir la complejidad de fusión en el peor de los casos a Θ (1); Esta técnica se aplica a cualquier estructura de datos del montón que tenga inserción en Θ (1) y find-max , delete-max , fusione en O (log n ).
^ Límite inferior de ^[12] límite superior de ^[13] $\Omega (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$
^ Brodal y Okasaki describen más tarde una variante persistente con los mismos límites excepto la tecla de disminución, que no es compatible. Los montones con n elementos se pueden construir de abajo hacia arriba en O ( n ). ^[18]

Aplicaciones

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

Heapsort : uno de los mejores métodos de clasificación está implementado y sin los peores escenarios cuadráticos.
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 késimo elemento) se pueden realizar en tiempo sublineal sobre los datos que están en un montón. ^[20]
Algoritmos gráficos : al utilizar montones como estructuras de datos transversales internas, el tiempo de ejecución se reducirá en orden polinómico. Ejemplos de tales 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 vinculada o una matriz, una cola de prioridad se puede implementar con un montón o una variedad de otros métodos.
Fusión 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. Los ejemplos de la necesidad de fusionar incluyen la clasificación externa y la transmisión de resultados de datos distribuidos, como un árbol de fusión estructurado de registros. 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 filtrado del montón. (Como alternativa, 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 montones (generalmente implementados como montones binarios), que operan en iteradores de acceso aleatorio arbitrarios . Trata los iteradores como una referencia a una matriz y utiliza la conversión de matriz a montón. También proporciona el adaptador de contenedor Priority_queue , que envuelve estas instalaciones en una clase similar a un contenedor. Sin embargo, no existe soporte estándar para las operaciones clave de reemplazo, filtrado hacia arriba/desplazado o disminución/aumento.
Las bibliotecas de Boost C++ incluyen una biblioteca de montones. A diferencia de STL, admite operaciones de disminución y aumento, y admite tipos adicionales de montón: específicamente, admite montones d -ario, binomial, Fibonacci, emparejamiento y sesgo.
Existe una implementación de montón genérica para C y C++ con soporte para montón D-ary y B-heap . 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 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 declaraciones foreach integradas de D y la integración con la API basada en rango 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 por defecto 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 tecla reemplazar, filtrar hacia arriba/abajo o disminuir/aumentar.
Python tiene un módulo heapq que implementa una cola de prioridad utilizando un montón binario. La biblioteca expone una función de lugar de almacenamiento dinámico para admitir la fusión de k vías.
PHP tiene max-heap ( SplMaxHeap ) y min-heap ( SplMinHeap ) a partir de la versión 5.3 en la biblioteca PHP estándar.
Perl tiene implementaciones de montones 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 en un tipo arbitrario que satisface una interfaz determinada. Ese paquete no admite las operaciones de tecla reemplazar, filtrar hacia arriba/abajo o disminuir/aumentar.
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. Se utiliza un montón en la implementación del bucle de eventos del temporizador.
El lenguaje de programación Rust tiene una implementación binaria de montón máximo, BinaryHeap, en el módulo de colecciones de su biblioteca estándar.
.NET tiene la clase PriorityQueue que utiliza una implementación de montón mínimo cuaternario (d-ary). Está disponible desde .NET 6.

Ver también

Algoritmo de clasificación
Estructura de datos de búsqueda
Pila (tipo de datos abstractos)
Cola (tipo de datos abstractos)
Árbol (estructura de datos)
Treap , una forma de árbol de búsqueda binario basado en árboles ordenados en montón

Referencias

^ Negro (ed.), Paul E. (14 de diciembre de 2004). Entrada para montón en Diccionario de algoritmos y estructuras de datos . Versión en línea. Instituto Nacional de Estándares y Tecnología de EE. UU. , 14 de diciembre de 2004. Consultado el 8 de octubre de 2017 en https://xlinux.nist.gov/dads/HTML/heap.html.
^ CORMEN, THOMAS H. (2009). INTRODUCCIÓN A LOS ALGORITMOS . Estados Unidos de América: The MIT Press Cambridge, Massachusetts Londres, Inglaterra. págs. 151-152. ISBN 978-0-262-03384-8.
^ Williams, JWJ (1964), "Algoritmo 232 - Heapsort", Comunicaciones de la ACM , 7 (6): 347–348, doi :10.1145/512274.512284
^ La biblioteca estándar de Python, 8.4. heapq — Algoritmo de cola de montón, heapq.heappush
^ La biblioteca estándar de Python, 8.4. heapq — Algoritmo de cola de montón, heapq.heappop
^ La biblioteca estándar de Python, 8.4. heapq — Algoritmo de cola de montón, heapq.heapreplace
^ 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 , IOS Press, 120 (1): 75–92, doi :10.3233/FI-2012-751.
^ abcd 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.
^ "Montón binomial | Wiki brillante de matemáticas y ciencias". brillante.org . Consultado el 30 de septiembre de 2019 .
^ 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
^ Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. Séptimo taller escandinavo sobre teoría de algoritmos (PDF) , Apuntes de conferencias sobre 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
^ Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia del emparejamiento de montones y estructuras de datos relacionadas" (PDF) . Revista de la Asociación de Maquinaria de Computación . 46 (4): 473–501. doi :10.1145/320211.320214.
^ Pettie, Seth (2005). Hacia un análisis final de los montones de emparejamiento (PDF) . FOCS '05 Actas del 46º Simposio anual del IEEE sobre fundamentos de la informática. págs. 174-183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
^ 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.
^ 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 de Computación . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874.
^ Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones estrictos de Fibonacci (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.
^ Brodal, Gerth S. (1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Proc. Séptimo Simposio anual ACM-SIAM sobre algoritmos discretos , págs. 52–58
^ Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montón ascendente". Estructuras de datos y algoritmos en Java (3ª ed.). págs. 338–341. ISBN 0-471-46983-1.
^ Takaoka, Tadao (1999), Teoría de 2 a 3 montones (PDF) , p. 12
^ Frederickson, Greg N. (1993), "Un algoritmo óptimo para la selección en un montón mínimo", 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 3 de diciembre de 2012 , consultado el 31 de octubre de 2010.

enlaces externos

Wikimedia Commons tiene medios relacionados con las estructuras de datos del montón .

Wikibook Data Structures tiene una página sobre el tema: Montones mínimos y máximos.

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