El montón d -ario o d -heap es una estructura de datos de cola de prioridad , una generalización del montón binario en el que los nodos tienen d hijos en lugar de 2. [1] [2] [3] Por lo tanto, un montón binario es un 2 -montón, y un montón ternario es un montón de 3. Según Tarjan [2] y Jensen et al., [4] Donald B. Johnson inventó los montones d -arios en 1975. [1]
Esta estructura de datos permite que las operaciones de disminución de prioridad se realicen más rápidamente que los montones binarios, a expensas de operaciones mínimas de eliminación 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 montones d -arios tienen un mejor comportamiento de memoria caché que los montones binarios, lo que les permite ejecutarse más rápidamente en la práctica a pesar de tener un tiempo de ejecución teóricamente mayor en el peor de los casos. [6] Al igual que los montones binarios, los montones d -arios son una estructura de datos local que no utiliza almacenamiento adicional más allá del necesario para almacenar la matriz de elementos en el montón. [2] [7]
El montón d -ario consta de una matriz de n elementos, cada uno de los cuales tiene una prioridad asociada. Estos elementos pueden verse como los nodos de un árbol d -ario completo, enumerados en primer orden transversal : 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 hasta 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 su Los hijos son los elementos en las posiciones di + 1 a di + d . Según 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 montón mínimo (o el elemento de prioridad máxima en un montón máximo) 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 de 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 montón, el elemento x se intercambia con uno de sus hijos (el que tiene la prioridad más pequeña en un montón mínimo, o el que tiene la prioridad más grande en un montón máximo) , moviéndolo hacia abajo en el árbol y luego en la matriz, hasta que finalmente se cumpla la propiedad del montón. Se puede utilizar el mismo procedimiento de intercambio descendente 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. [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 más temprano en la matriz, hasta que finalmente el La propiedad del montón se cumple. Se puede utilizar el mismo procedimiento de intercambio ascendente 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 pueden 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, tanto el procedimiento de intercambio ascendente como el procedimiento de intercambio descendente pueden realizar tantos intercambios como log d n = log n / log d . En el procedimiento de intercambio al alza, cada intercambio implica una única comparación de un artículo con su elemento principal y requiere un tiempo constante. Por lo tanto, el tiempo para insertar un nuevo elemento en el montón, disminuir la prioridad de un elemento en un montón mínimo o aumentar la prioridad de un elemento en un montón máximo es O(log n / log d ) . En el procedimiento de intercambio a la baja, cada intercambio implica d comparaciones y toma 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 es necesario un intercambio. . Por lo tanto, el tiempo para eliminar el elemento raíz, aumentar la prioridad de un elemento en un montón mínimo o 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 pueden intercambiarse hacia abajo al menos una vez, a un costo de O( d ) tiempo para encontrar al niño con quien intercambiarlos. Como máximo, n / d 2 + 1 nodos pueden intercambiarse hacia abajo dos veces, incurriendo en un costo O( d ) adicional para el segundo intercambio más allá del costo ya contado 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 para
para d = 3.
El uso de espacio del montón d -ary , con operaciones de inserción y eliminación mínima, es lineal, ya que no utiliza almacenamiento adicional aparte de una matriz que contiene una lista de los elementos del montón. [2] [7] Si es necesario admitir cambios en las prioridades de los elementos existentes, entonces también se deben mantener punteros de los elementos a sus posiciones en el montón, que nuevamente utiliza solo almacenamiento lineal. [2]
Cuando se opera en un gráfico con m aristas yn 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 montón mínimo en el que hay n operaciones de eliminación mínima y hasta m operaciones de disminución de prioridad. Al utilizar un montón 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, un mejora con respecto al tiempo de ejecución O ( m log n ) de las versiones de montón binario de estos algoritmos siempre que el número de aristas es significativamente mayor que el número de vértices. [1] [5] Una estructura de datos de cola de prioridad alternativa, el montón 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 montones d -arios son generalmente al menos tan rápidos, y a menudo más rápido que los montones de Fibonacci para esta aplicación. [9]
Los 4 montones pueden funcionar mejor que los binarios en la práctica, incluso para operaciones de eliminación mínima. [2] [3] Además, un montón d -ary generalmente 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 generalmente requiere más errores de caché y fallas de página de memoria virtual que un d montón -ario, cada uno de los cuales requiere 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]
