montón d -ary

El montón d -ary 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 -heap, 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 -ary tienen un mejor comportamiento de caché de memoria 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 -ary 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]}

Estructura de datos

El montón d -ary consta de 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 completo, enumerados en primer orden transversal de 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 hasta d son sus hijos, los siguientes d ² 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 . 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 que el elemento x y sus elementos secundarios no satisfacen la propiedad del montón, el elemento x se intercambia con uno de sus elementos secundarios (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 satisfaga la propiedad del montón. El mismo procedimiento de intercambio descendente se puede utilizar para aumentar la prioridad de un elemento en un montón mínimo, o para disminuir la prioridad de un artículo 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 antes en la matriz, hasta que finalmente el la propiedad del montón está satisfecha. El mismo procedimiento de intercambio ascendente se puede utilizar para disminuir la prioridad de un elemento en un montón mínimo o para aumentar la prioridad de un artículo en un montón máximo. ^{[2] [3]}

Para crear un nuevo montón a partir de una matriz de n elementos, uno 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]}

Análisis

En un montón d -ary con n elementos en él, tanto el procedimiento de intercambio hacia arriba como el procedimiento de intercambio hacia abajo pueden realizar tantos cambios como log _d n = log n / log d . En el procedimiento de intercambio ascendente, cada intercambio implica una única comparación de un artículo 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 toma O ( d) tiempo: se necesitan comparaciones d - 1 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, 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 -ary 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 -ary, y no se realiza ningún intercambio descendente para esos elementos. Como máximo, los artículos n / d + 1 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 ² + 1 nodos se pueden intercambiar hacia abajo dos veces, incurriendo en un O ( d ) adicional costo 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

${\displaystyle \sum _{i=1}^{\log _{d}n}\left({\frac {n}{d^{i}}}+1\right)O(d)=O(n).}$^{[2] [3]}

Se sabe que el valor exacto de lo anterior (el número de comparaciones en el peor de los casos durante la construcción de la pila d-aria) es igual a:

${\displaystyle {\frac {d}{d-1}}(n-s_{d}(n))-(d-1-(n{\bmod {d}}))\left(e_{d}\left(\left\lfloor {\frac {n}{d}}\right\rfloor \right)+1\right)}$, ^[8]

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

${\displaystyle 2n-2s_{2}(n)-e_{2}(n)}$, ^[8]

para d = 2, y para

${\displaystyle {\frac {3}{2}}(n-s_{3}(n))-2e_{3}(n)-e_{3}(n-1)}$, ^[8]

para d = 3.

El uso de espacio del montón d -ary , con las operaciones insert y delete-min, es lineal, ya que no utiliza almacenamiento adicional más que 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, también se deben mantener los indicadores de los elementos a sus posiciones en el montón, que de nuevo utiliza sólo almacenamiento lineal. ^[2]

Aplicaciones

Cuando se opera en un gráfico con m bordes y n vértices, tanto el algoritmo de Dijkstra para las rutas más cortas como el algoritmo de Prim para los árboles de expansión mínimos usan un min-heap en el que hay n operaciones delete-min y tantas como m operaciones de prioridad decreciente. Al usar un montón d -ary 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 con respecto al tiempo de ejecución O ( m log n ) de las versiones de pila binaria 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 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 -ary 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 montones binarios en la práctica, incluso para operaciones delete-min. ^{[2] [3]} Además, un montón d -ary 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 fallas de caché y fallas de página de memoria virtual que un d -ary heap, cada uno de los cuales toma mucho más tiempo que el trabajo extra incurrido por las comparaciones adicionales que hace un d -ary heap en comparación con un montón binario. ^{[6] [10]}

Referencias

1. Johnson, DB (1975), "Colas de prioridad con actualización y búsqueda de árboles de expansión mínimos", Cartas de procesamiento de información , 4 (3): 53–57, doi : 10.1016 / 0020-0190 (75) 90001-0.
2. Tarjan, RE (1983), "3.2. d- montones", Estructuras de datos y algoritmos de red , Serie de conferencias regionales CBMS-NSF en Matemáticas aplicadas, 44 , Sociedad para industrias y Matemáticas aplicadas , págs. 34–38. Tenga en cuenta que Tarjan usa numeración basada en 1, no numeración basada en 0, por lo que sus fórmulas para el padre y los hijos de un nodo deben ajustarse cuando se usa la numeración basada en 0.
3. Weiss, MA (2007), " d- montones", Estructuras de datos y análisis de algoritmos (2ª ed.), Addison-Wesley, p. 216, ISBN 0-321-37013-9.
4. Jensen, C .; Katajainen, J .; Vitale, F. (2004), Una verdad extendida sobre montones (PDF) .
5. Tarjan (1983) , págs. 77 y 91.
6. Naor, D .; Martel, CU; Matloff, NS (octubre de 1991), "Rendimiento de las estructuras de colas de prioridad en un entorno de memoria virtual", Computer Journal , 34 (5): 428–437, doi : 10.1093 / comjnl / 34.5.428.
7. Mortensen, CW; Pettie, S. (2005), "La complejidad de las colas de prioridad implícitas y eficientes en el espacio", Algoritmos y estructuras de datos: 9º Taller Internacional, WADS 2005, Waterloo, Canadá, 15-17 de agosto de 2005, Actas , Notas de conferencias en Ciencias de la Computación , 3608 , Springer-Verlag, págs. 49–60, doi : 10.1007 / 11534273_6 , ISBN 978-3-540-28101-6.
8. 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.
9. Cherkassky, Boris V .; Goldberg, Andrew V .; Radzik, Tomasz (mayo de 1996), "Algoritmos de rutas más cortas: teoría y evaluación experimental" , Programación matemática , 73 (2): 129-174, CiteSeerX 10.1.1.48.752 , doi : 10.1007 / BF02592101 .
10. Kamp, Poul-Henning (11 de junio de 2010), "Lo estás haciendo mal" , Cola de ACM , 8 (6).

Enlaces externos

• Implementación de C ++ de montón generalizado con soporte de D-Heap