El montón d -ario o montón d es una estructura de datos de cola de prioridad , una generalización del montón binario en la que los nodos tienen d hijos en lugar de 2. [1] [2] [3] Por lo tanto, un montón binario es un montón de 2 y un montón ternario es un montón de 3. Según Tarjan [2] y Jensen et al., [4] los montones d -arios fueron inventados por Donald B. Johnson en 1975. [1]
Esta estructura de datos permite que las operaciones de disminución de prioridad se realicen más rápidamente que los montículos binarios, a expensas de operaciones de eliminación mínima más lentas. Esta compensación conduce a mejores tiempos de ejecución para algoritmos como el algoritmo de Dijkstra en el que las operaciones de disminución de prioridad son más comunes que las operaciones de eliminación mínima. [1] [5] Además, los montículos d -arios tienen un mejor comportamiento de caché de memoria que los montículos binarios, lo que les permite ejecutarse más rápidamente en la práctica a pesar de tener un tiempo de ejecución en el peor de los casos teóricamente mayor. [6] Al igual que los montículos binarios, los montículos d -arios son una estructura de datos in situ que no utiliza almacenamiento adicional más allá del necesario para almacenar la matriz de elementos en el montículo. [2] [7]
El montón d -ario consiste en una matriz de n elementos, cada uno de los cuales tiene una prioridad asociada. Estos elementos pueden verse como los nodos en un árbol d -ario completo, listados en orden de recorrido en amplitud : el elemento en la posición 0 de la matriz (usando numeración basada en cero ) forma la raíz del árbol, los elementos en las posiciones 1 a d son sus hijos, los siguientes d 2 elementos son sus nietos, etc. Por lo tanto, el padre del elemento en la posición i (para cualquier i > 0 ) es el elemento en la posición ⌊ ( i − 1)/ d ⌋ y sus hijos son los elementos en las posiciones di + 1 a di + d . De acuerdo con la propiedad del montón , en un montón mínimo, cada elemento tiene una prioridad que es al menos tan grande como su padre; en un montón máximo, cada elemento tiene una prioridad que no es mayor que su padre. [2] [3]
El elemento de prioridad mínima en un min-heap (o el elemento de prioridad máxima en un max-heap) siempre se puede encontrar en la posición 0 de la matriz. Para eliminar este elemento de la cola de prioridad, el último elemento x en la matriz se mueve a su lugar, y la longitud de la matriz se reduce en uno. Luego, mientras el elemento x y sus hijos no satisfacen la propiedad del heap, el elemento x se intercambia con uno de sus hijos (el que tiene la prioridad más pequeña en un min-heap, o el que tiene la prioridad más grande en un max-heap), moviéndolo hacia abajo en el árbol y luego en la matriz, hasta que finalmente se satisface la propiedad del heap. El mismo procedimiento de intercambio hacia abajo se puede utilizar para aumentar la prioridad de un elemento en un min-heap, o para disminuir la prioridad de un elemento en un max-heap. [2] [3]
Para insertar un nuevo elemento en el montón, el elemento se agrega al final de la matriz y, luego, mientras se viola la propiedad del montón, se intercambia con su padre, moviéndolo hacia arriba en el árbol y antes en la matriz, hasta que finalmente se satisface la propiedad del montón. El mismo procedimiento de intercambio hacia arriba se puede utilizar para disminuir la prioridad de un elemento en un montón mínimo o para aumentar la prioridad de un elemento en un montón máximo. [2] [3]
Para crear un nuevo montón a partir de una matriz de n elementos, se puede recorrer los elementos en orden inverso, comenzando desde el elemento en la posición n − 1 y terminando en el elemento en la posición 0, aplicando el procedimiento de intercambio descendente para cada elemento. [2] [3]
En un montón d -ario con n elementos en él, tanto el procedimiento de intercambio ascendente como el de intercambio descendente pueden realizar tantos intercambios como log d n = log n / log d . En el procedimiento de intercambio ascendente, cada intercambio implica una única comparación de un elemento con su padre y lleva un tiempo constante. Por lo tanto, el tiempo para insertar un nuevo elemento en el montón, para disminuir la prioridad de un elemento en un montón mínimo o para aumentar la prioridad de un elemento en un montón máximo es O(log n / log d ) . En el procedimiento de intercambio descendente, cada intercambio implica d comparaciones y lleva O( d ) tiempo: se necesitan d − 1 comparaciones para determinar el mínimo o máximo de los hijos y luego una comparación más con el padre para determinar si se necesita un intercambio. Por lo tanto, el tiempo para eliminar el elemento raíz, para aumentar la prioridad de un elemento en un montón mínimo o para disminuir la prioridad de un elemento en un montón máximo es O( d log n / log d ) . [2] [3]
Al crear un montón d -ario a partir de un conjunto de n elementos, la mayoría de los elementos están en posiciones que eventualmente contendrán hojas del árbol d -ario, y no se realiza ningún intercambio descendente para esos elementos. Como máximo n / d + 1 elementos no son hojas, y se pueden intercambiar hacia abajo al menos una vez, a un costo de O( d ) tiempo para encontrar el hijo con el que intercambiarlos. Como máximo n / d 2 + 1 nodos se pueden intercambiar hacia abajo dos veces, incurriendo en un costo adicional de O( d ) para el segundo intercambio más allá del costo ya contabilizado en el primer término, etc. Por lo tanto, la cantidad total de tiempo para crear un montón de esta manera es
Se sabe que el valor exacto de lo anterior (el número de comparaciones en el peor de los casos durante la construcción del montón d-ario) es igual a:
donde s d (n) es la suma de todos los dígitos de la representación estándar en base d de n y e d (n) es el exponente de d en la factorización de n. Esto se reduce a
para d = 2, y a
para d = 3.
El uso del espacio del montón d -ario , con operaciones de inserción y eliminación mínima, es lineal, ya que no utiliza almacenamiento adicional más que una matriz que contiene una lista de los elementos en el montón. [2] [7] Si se necesitan soportar cambios en las prioridades de los elementos existentes, entonces también se deben mantener punteros desde los elementos a sus posiciones en el montón, que nuevamente utiliza solo almacenamiento lineal. [2]
Al operar en un grafo con m aristas y n vértices, tanto el algoritmo de Dijkstra para caminos más cortos como el algoritmo de Prim para árboles de expansión mínima utilizan un min-heap en el que hay n operaciones de eliminación mínima y hasta m operaciones de disminución de prioridad. Al utilizar un heap d -ario con d = m / n , los tiempos totales para estos dos tipos de operaciones pueden equilibrarse entre sí, lo que lleva a un tiempo total de O( m log m / n n ) para el algoritmo, una mejora sobre el tiempo de ejecución O( m log n ) de las versiones de heap binario de estos algoritmos siempre que el número de aristas sea significativamente mayor que el número de vértices. [1] [5] Una estructura de datos de cola de prioridad alternativa, el heap de Fibonacci , proporciona un tiempo de ejecución teórico aún mejor de O( m + n log n ) , pero en la práctica los heaps d -arios son generalmente al menos tan rápidos, y a menudo más rápidos, que los heaps de Fibonacci para esta aplicación. [9]
En la práctica, los 4-montones pueden tener un mejor rendimiento que los montículos binarios, incluso para operaciones de eliminación mínima. [2] [3] Además, un montón d -ario normalmente se ejecuta mucho más rápido que un montón binario para tamaños de montón que exceden el tamaño de la memoria caché de la computadora : un montón binario normalmente requiere más errores de caché y errores de página de memoria virtual que un montón d -ario, cada uno de los cuales toma mucho más tiempo que el trabajo adicional incurrido por las comparaciones adicionales que hace un montón d -ario en comparación con un montón binario. [6] [10]
