Montón (estructura de datos)

Compartir Imprimir Citar

Estructura de datos de ciencias informáticas

Ejemplo de un max-heap binario con teclas de nodo siendo enteros entre 1 y 100

En informática, un montón es una estructura de datos basada en un árbol especializado que es esencialmente un árbol casi completo que satisface la propiedad del montón: en un max heap, para cualquier nodo C dado, si P es un nodo principal de C, entonces la clave (el valor) de P es mayor o igual que la clave de C. En un min heap, la clave de P es menor o igual que la clave de C. El nodo en el "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 abstractos 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 prioridad más alta (o más baja) siempre se almacena en la raíz. Sin embargo, un montón no es una estructura ordenada; puede considerarse como 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 las 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 (ver figura). La estructura de datos del montón, específicamente el montón binario, fue introducida por J. W. J. Williams en 1964, como una estructura de datos para el algoritmo de clasificación heapsort. 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 a ramas para cada nodo siempre tiene log_una N altura.

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 lo habría, por ejemplo, en un árbol de búsqueda binaria). La relación de montón mencionada anteriormente se aplica solo entre los nodos y sus padres, abuelos, etc. El número máximo de hijos que puede tener cada nodo depende del tipo de montón.

Operaciones

Las operaciones comunes que involucran montones son:

Básico

encontrar-max (o find-min): encontrar un ítem máximo de un salto máximo, o un ítem mínimo de un min-heap, respectivamente (a.k.a. Peek)
insertar: añadiendo una nueva llave al montón (a.k.a., empujar)
extracto-max (o extracto-min): devuelve el nodo de valor máximo de un monto máximo [o valor mínimo de un monto mínimo] después de retirarlo del montón (a.k.a., pop)
delete-max (o eliminar-min): eliminar el nodo raíz de un montón máximo (o salto min), respectivamente
reemplazar: pop root y empuja una nueva llave. Más eficiente que el pop seguido por el empuje, ya que sólo tiene que equilibrar una vez, no dos veces, y apropiado para los montos fijos.

Creación

crear-heap: crear un montón vacío
heapify: crear un montón de elementos
merge ()sindicato): unir dos montones para formar un nuevo montón válido que contiene todos los elementos de ambos, preservando los montones originales.
sold: unir dos montones para formar un nuevo montón válido que contiene todos los elementos de ambos, destruyendo los montones originales.

Inspección

tamaño: devolver el número de artículos en el montón.
Está vacío.: volver verdadero si el montón está vacío, falso de otro modo.

Internos

aumento de la llave o disminucion-key: actualización de una llave dentro de un max- o min-heap, respectivamente
Borrador: eliminar un nodo arbitrario (seguida por mover el último nodo y el sifting para mantener el montón)
sift-up: mover un nodo en el árbol, siempre y cuando sea necesario; utilizado para restaurar la condición del montón después de la inserción. Se llama "sift" porque el nodo se mueve por el árbol hasta que alcanza el nivel correcto, como en un tamiz.
sift-down: mover un nodo abajo en el árbol, similar al sift-up; utilizado 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 / niño se define implícitamente por los índices de elementos en el array.

Ejemplo de un max-heap binario completo con teclas de nodo siendo enteros de 1 a 100 y cómo se almacenaría en un array.

Para un montón binario, en el array, el primer índice contiene el elemento raíz. Los siguientes dos índices de la matriz contienen los hijos de la raíz. Los siguientes cuatro índices contienen los cuatro hijos de los dos nudos de la raíz, y así sucesivamente. Por lo tanto, dado un nodo en el índice $i$ , sus hijos están en índices $2i+1$ y ${displaystyle 2i+2}$ , y su padre está en el índice $⌊ i -1)/2$ . Este esquema de indexación simple hace que sea eficiente para mover "up" o "down" el árbol.

El equilibrio de un montón se realiza mediante operaciones de cribado ascendente o descendente (intercambio de elementos que están fuera de servicio). 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, la propiedad del montón puede violarse 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: Añadir el nuevo elemento al final del montón, en el primer espacio libre disponible. Si esto va a violar la propiedad de la pila, presione el nuevo elemento (nadando operación) hasta que se haya restablecido la propiedad de la pila.
Extracción: Quitar la raíz e insertar el último elemento del montón en la raíz. Si esto viola la propiedad de la pila, presione la nueva raíz (fregadero operación) para restablecer la propiedad del montón.
Sustitución: Quitar la raíz y poner la nuevo elemento en la raíz y sift hacia abajo. Cuando se compara con la extracción seguida por la inserción, esto evita un sift hacia arriba paso.

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 usando el clásico algoritmo de Floyd, con el número de comparaciones en el peor de los casos igual a 2N − 2s₂(N) − e₂(N) (para un montón binario), donde s₂(N) es el la suma de todos los dígitos de la representación binaria de N y e₂(N) es el exponente de 2 en la descomposición en factores primos de N. Esto es más rápido que una secuencia de inserciones consecutivas en un montón originalmente vacío, que es logarítmicamente lineal.

Variantes

2-3 montones
B-heap
Beap
Salto binario
Salto binomio
Oficina de redacción
d-ary heap
Fibonacci heap
K-D Heap
Leaf heap
Salto de izquierda
Salto de pareja
Salto de radiación
Salto soldable aleatorio
Skew Heap
Jabón suave
Ternario
Treap
Montón débil

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

Estas son las complejidades de tiempo de varias estructuras de datos de almacenamiento dinámico. Los nombres de funciones asumen un montón máximo. Para el significado de "O(f)" y "Θ(f)" ver notación Big O.

Operación	encontrar-max	delete-max	insertar	aumento de la llave	sold
binario	.1)	.(logn)	O(logn)	O(logn)	.()n)
Izquierda	.1)	.(log n)	.(log n)	O(log n)	.(log n)
Binomial	.1)	.(log n)	.1)	.(log n)	O(logn)
Fibonacci	.1)	O(logn)	.1)	.1)	.1)
Pareja	.1)	O(log n)	.1)	o(logn)	.1)
Brodal	.1)	O(logn)	.1)	.1)	.1)
Rank-pairing	.1)	O(log n)	.1)	.1)	.1)
Fibonacci estricta	.1)	O(log n)	.1)	.1)	.1)
2-3 montones	O(log n)	O(log n)	O(log n)	.1)	?

^ Cada inserción toma O(log)k) en el tamaño existente del montón, por lo tanto $sum _{k=1}^{n}O(log k)$ . Desde $log n/2=(log n)-1$ , un factor constante (la mitad) de estas inserciones están dentro de un factor constante del máximo, por lo que asintomáticamente podemos asumir $k=n$ ; formalmente el tiempo es $nO(log n)-O(n)=O(nlog n)$ . Esto también se puede ver fácilmente desde la aproximación de Stirling.
^ a b c d e f g h i Tiempo amortizado.
^ n es el tamaño del montón más grande.
^ Límite inferior de ${displaystyle Omega (log log n),}$ límite superior ${displaystyle O(2^{2{sqrt {log log n}}}).}$
^ Brodal y Okasaki describen más adelante una variante persistente con los mismos límites excepto la tecla de reducción, que no es compatible. Saltos con n elementos pueden ser construidos en el fondo O()n).

Aplicaciones

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

Heapsort: Uno de los mejores métodos de clasificación es estar en el lugar y sin escenarios cuadráticos peores.
algoritmos de selección: Un montón permite el acceso al elemento min o max en tiempo constante, y otras selecciones (como mediana o kth-element) se pueden hacer en tiempo sub-lineal en datos que está en un montón.
algoritmos de Gráfico: Mediante el uso de montones como estructuras de datos traversales internas, el tiempo de ejecución se reducirá por orden polinomio. Ejemplos de estos problemas son el algoritmo de árbol de tamaño mínimo de Prim y el algoritmo más corto de Dijkstra.
Priority Queue: Una cola prioritaria es un concepto abstracto como "una lista" o "un mapa"; así como una lista puede ser implementada con una lista vinculada o una matriz, una cola prioritaria puede ser implementada con un montón o una variedad de otros métodos.
K-way merge: Una estructura de datos de montón es útil para combinar muchos flujos de entrada ya surtidos en una única secuencia de salida ordenada. Ejemplos de la necesidad de fusionarse incluyen la clasificación externa y los resultados de streaming de datos distribuidos como un árbol de fusión estructurado de troncos. El bucle interior está obteniendo el elemento min, sustituyendo por el siguiente elemento para el flujo de entrada correspondiente, luego haciendo una operación de salto de sift hacia abajo. (Sustituir alternativamente la función). (Usar funciones de extracto-max e insertar de una cola prioritaria son mucho menos eficientes.)
Estadísticas del orden: La estructura de datos Heap se puede utilizar para encontrar eficientemente el elemento kth más pequeño (o mayor) en un array.

Implementaciones de lenguajes de programación

La Biblioteca Estándar C+ ofrece make_heap, push_heap y Pop_heap algoritmos para montones (generalmente implementados como montones binarios), que operan en iteradores arbitrarios de acceso aleatorio. Trata a los iteradores como referencia a un array, y utiliza la conversión de array-a-heap. También proporciona el adaptador de contenedores priority_queue, que envuelve estas instalaciones en una clase tipo contenedor. Sin embargo, no hay soporte estándar para las operaciones de sustitución, sift-up/sift-down o disminución/aumento-key.
Las bibliotecas Boost C++ incluyen una biblioteca de montones. A diferencia del STL, soporta la disminución y el aumento de operaciones, y soporta otros tipos de salto: específicamente, soporta d- Cuervos diarios, binomiales, Fibonacci, emparejados y bisturí.
Hay una aplicación de heap genérica para C y C++ con soporte D-ary de heap 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 instalaciones se pueden construir desde cualquier rango de acceso aleatorio. Bing expone una interfaz de rango de entrada que permite la iteración con D incorporado en adelante declaraciones e integración con la API basada en rango del paquete std.algorithm.
Para Haskell hay los datos. Módulo de salto.
La plataforma Java (desde la versión 1.5) proporciona una implementación de montones binarios con la clase java.util.PriorityQueue en Java Collections Framework. Esta clase implementa por defecto un min-heap; para implementar un max-heap, programador debe escribir un comparador personalizado. No hay apoyo para las operaciones de sustitución, sift-up/sift-down, o disminución/aumento-key.
Python tiene un módulo heapq que implementa una cola prioritaria usando un montón binario. La biblioteca expone una función heapreplace para apoyar k-way merging.
PHP tiene ambos max-heap (SplMaxHeap) y min-heap (SplMinHeap) a la versión 5.3 en la Biblioteca Estándar PHP.
Perl tiene implementaciones de montones binarios, binomiales y Fibonacci en la distribución Heap disponible en CPAN.
El lenguaje Go contiene un paquete de heap con algoritmos de heap que operan en un tipo arbitrario que satisface una interfaz dada. Ese paquete no apoya las operaciones de sustitución, sift-up/sift-down, o disminución/aumento-key.
La biblioteca de la Fundación Core de Apple contiene una estructura CFBinaryHeap.
Pharo tiene una implementación de un montón en el paquete Colecciones-Secuenciable junto con un conjunto de casos de prueba. Se utiliza un montón en la implementación del bucle de evento timer.
El lenguaje de programación Rust tiene una implementación binaria de max-heap, BinaryHeap, en el colecciones módulo de su biblioteca estándar.
. NET tiene la clase PriorityQueue que utiliza la implementación trimestral (d-ary) de min-heap. Está disponible. NET 6.