Heap (estructura de datos) - Heap (data structure)

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

En informática , un montón es una estructura de datos especializada basada en árboles que es esencialmente un árbol casi completo 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. 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 puedan implementar. 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; se puede considerar 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).

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 JWJ Williams en 1964, como una estructura de datos para el algoritmo de clasificación de 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 para cada nodo una rama siempre tiene log _una altura de 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 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

• 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 empujar )
• 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 )
• delete-max (o delete-min ): eliminando el nodo raíz de un montón máximo (o montón mínimo), respectivamente
• reemplazar : pop root y presione una nueva tecla. Más eficiente que el pop seguido de push, ya que solo es necesario equilibrarlo una vez, no dos, y es apropiado para montones de tamaño fijo.

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 contiene todos los elementos de ambos, conservando los montones originales.
• meld : 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 : 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 : eliminar un nodo arbitrario (seguido de mover el último nodo y tamizar para mantener el montón)
• tamizar : mover un nodo hacia arriba en el árbol, tanto tiempo como sea necesario; utilizado 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 que alcanza 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 el 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 enteras de 1 a 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 siguientes dos índices 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 2i + 1 y 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 (intercambiando 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 que un elemento se inserta o se elimina de un montón, la propiedad del montón se puede violar y el montón debe reequilibrarse intercambiando elementos dentro de la matriz.

Aunque diferentes tipos de montones implementan las operaciones de manera diferente, la forma más común es la siguiente:
Inserción: agregue el nuevo elemento al final del montón, en el primer espacio libre disponible. Esto violará la propiedad del montón, por lo que los elementos se desplazarán hacia arriba (o la 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 y esto violará la propiedad del montón, por lo tanto, tamice para restablecer la propiedad del montón (o la operación de sumidero ). Por lo tanto, el reemplazo se realiza eliminando la raíz y colocando el nuevo elemento en la raíz y tamizando hacia abajo, evitando un paso de tamizado hacia arriba en comparación con el pop (tamizar hacia abajo el último elemento) seguido de empujar (tamizar hacia arriba el nuevo elemento).

La construcción de un montón binario (o d -ary) 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 una pila binaria), 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 en primos de N . Esto es más rápido que una secuencia de inserciones consecutivas en un montón originalmente vacío, que es log-lineal.

Variantes

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

A continuación, se muestran las complejidades temporales de varias estructuras de datos de pila. Los nombres de las funciones asumen un montón máximo. Para el significado de " O ( f )" y " Θ ( f )" ver Big O notación .

Aplicaciones

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

• Heapsort : uno de los mejores métodos de clasificación está en el lugar y sin escenarios cuadráticos del peor de los casos.
• 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 sub-lineal en los datos que están en un montón.
• Algoritmos de gráficos : al utilizar montones como estructuras de datos transversales internas, el tiempo de ejecución se reducirá por orden polinómico. Ejemplos de tales problemas son el algoritmo de árbol de expansión mínimo 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 pila es útil para fusionar muchos flujos de entrada ya ordenados en un solo flujo de salida ordenado. Los ejemplos de la necesidad de fusión incluyen la clasificación externa y la transmisión de resultados de datos distribuidos, como un árbol de fusión estructurado por 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 almacenamiento dinámico. (Alternativamente, la función de reemplazo). (El uso de las funciones extract-max e insertar de una cola de prioridad es mucho menos eficiente).
• Estadísticas de pedidos : la estructura de datos Heap se puede utilizar para encontrar de manera eficiente el k-ésimo elemento más pequeño (o más grande) en una matriz.

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 usa la conversión de matriz a pila. También proporciona el adaptador de contenedor priority_queue , que envuelve estas instalaciones en una clase similar a un contenedor. Sin embargo, no existe un soporte estándar para las operaciones de tecla reemplazar, tamizar hacia arriba / tamizar hacia abajo o disminuir / aumentar.
• Las bibliotecas de Boost C ++ incluyen una biblioteca de montones. A diferencia de STL, admite operaciones de aumento y disminución, y admite tipos adicionales de montón: específicamente, admite montones d -ary, binomial, Fibonacci, emparejamiento y sesgo.
• Hay una implementación de pila genérica para C y C ++ con soporte D-ary 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 D's rangos . 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 incorporadas de D y la integración con la API basada en rangos del paquete std.algorithm .
• La plataforma Java (desde la versión 1.5) proporciona una implementación de pila binaria con la clase java.util.PriorityQueueen el marco de colecciones de Java . Esta clase implementa por defecto un min-heap; para implementar un montón máximo, el programador debe escribir un comparador personalizado. No hay soporte para las operaciones de tecla reemplazar, tamizar hacia arriba / tamizar hacia abajo o disminuir / aumentar.
• Python tiene un módulo heapq que implementa una cola de prioridad usando un montón binario. La biblioteca expone una función de reemplazo de pila para admitir la fusión de k-way.
• PHP tiene max-heap ( SplMaxHeap ) y min-heap ( SplMinHeap ) a partir de la versión 5.3 en la biblioteca estándar de PHP.
• Perl tiene implementaciones de montones binarios, binomiales y de Fibonacci en la distribución Heap disponible en CPAN .
• El Go lenguaje contiene un montón paquete con algoritmos de montón que operan sobre un tipo arbitrario que satisface una interfaz dada. Ese paquete no es compatible con las operaciones de reemplazo, tamizar hacia arriba / tamizar hacia abajo o disminuir / aumentar la 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. Se utiliza un montón en la implementación del ciclo de eventos del temporizador.
• El lenguaje de programación Rust tiene una implementación binaria max-heap, BinaryHeap , en el módulo de colecciones de su biblioteca estándar.

Ver también

• Algoritmo de clasificació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 basada en árboles ordenados por montones

Referencias

enlaces externos

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