Montón de emparejamiento

Variante de la estructura de datos del montón

Un montón de emparejamiento es un tipo de estructura de datos de montón con una implementación relativamente simple y un excelente rendimiento amortizado práctico , introducido por Michael Fredman , Robert Sedgewick , Daniel Sleator y Robert Tarjan en 1986. ^[1] Los montones de emparejamiento son estructuras de árbol multidireccionales ordenadas por montón y pueden considerarse montones de Fibonacci simplificados . Se consideran una "opción robusta" para implementar algoritmos como el algoritmo MST de Prim , ^[2] y admiten las siguientes operaciones (asumiendo un montón mínimo):

• find-min : simplemente devuelve el elemento superior del montón.
• meld : compara los dos elementos raíz, el más pequeño sigue siendo la raíz del resultado, el elemento más grande y su subárbol se agregan como un hijo de esta raíz.
• insertar : crea un nuevo montón para el elemento insertado y lo fusiona con el montón original.
• clave de disminución (opcional): elimina el subárbol enraizado en la clave que se va a disminuir, reemplaza la clave con una clave más pequeña y luego fusiona el resultado nuevamente en el montón.
• delete-min : elimina la raíz y realiza fusiones repetidas de sus subárboles hasta que quede un solo árbol. Se emplean varias estrategias de fusión.

El análisis de la complejidad temporal de los montones de emparejamiento se inspiró inicialmente en el de los árboles splay . ^[1] El tiempo amortizado por delete-min es O (log n ) , y las operaciones find-min , meld e insert se ejecutan en tiempo O (1) . ^[3]

Cuando también se añade una operación de disminución de clave , la determinación del tiempo de ejecución asintótico preciso de los montones de emparejamiento ha resultado difícil. Inicialmente, se conjeturó sobre bases empíricas que la complejidad temporal de esta operación era O (1) , ^[4] pero Fredman demostró que el tiempo amortizado por disminución de clave es al menos para algunas secuencias de operaciones. ^[5] Utilizando un argumento de amortización diferente, Pettie demostró que insert , meld y decrease-key se ejecutan en tiempo amortizado, que es . ^[6] Más tarde, Elmasry introdujo elaboraciones de montones de emparejamiento (perezoso, consolidar) para los que la disminución de clave se ejecuta en tiempo amortizado y otras operaciones tienen límites amortizados óptimos, ^{[7] [8]} pero no se conoce ningún límite estricto para la estructura de datos original. ^{[3] [6]} ${\displaystyle \Omega (\log \log n)}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}})}$ ${\displaystyle o(\log n)}$ ${\displaystyle O(\log \log n)}$ ${\displaystyle \Theta (\log \log n)}$

Aunque el rendimiento asintótico de los montículos de emparejamiento es peor que otros algoritmos de cola de prioridad como los montículos de Fibonacci , que realizan la clave decreciente en tiempo amortizado, el rendimiento en la práctica es excelente. Jones ^[9] y Larkin, Sen y Tarjan ^[10] realizaron experimentos en montículos de emparejamiento y otras estructuras de datos de montículos. Concluyeron que los montículos d-arios como los montículos binarios son más rápidos que todas las demás implementaciones de montículos cuando no se necesita la operación de clave decreciente (y por lo tanto no hay necesidad de rastrear externamente la ubicación de los nodos en el montículo), pero que cuando se necesita la clave decreciente , los montículos de emparejamiento son a menudo más rápidos que los montículos d-arios y casi siempre más rápidos que otros montículos basados ​​en punteros, incluidas las estructuras de datos como los montículos de Fibonacci que son teóricamente más eficientes. Chen et al. ^[11] examinaron colas de prioridad específicamente para su uso con el algoritmo de Dijkstra y concluyeron que en casos normales, el uso de un montón d-ario sin clave de disminución (en lugar de duplicar nodos en el montón e ignorar instancias redundantes) resultó en un mejor rendimiento, a pesar de las garantías de rendimiento teóricas inferiores. ${\displaystyle O(1)}$

Estructura

Un montón de emparejamiento es un montón vacío o un árbol de emparejamiento que consta de un elemento raíz y una lista posiblemente vacía de árboles de emparejamiento. La propiedad de ordenación del montón requiere que el padre de cualquier nodo no sea mayor que el nodo mismo. La siguiente descripción supone un montón puramente funcional que no admite la operación de disminución de clave .

tipo PairingTree[Elem] = Heap(elem: Elem, subheaps: List[PairingTree[Elem]]) tipo PairingHeap[Elem] = Empty | PairingTree[Elem]

Una implementación basada en punteros para máquinas RAM , que admita la tecla de disminución , se puede lograr utilizando tres punteros por nodo, al representar los hijos de un nodo mediante una lista doblemente enlazada : un puntero al primer hijo del nodo, uno a su próximo hermano y uno a su hermano anterior (o, para el hermano más a la izquierda, a su padre). También se puede ver como una variante de un árbol binario de hijo izquierdo hermano derecho con un puntero adicional al padre de un nodo (que representa a su hermano anterior o padre actual para el hermano más a la izquierda). Alternativamente, se puede omitir el puntero anterior dejando que el último hijo apunte de nuevo al padre, si se agrega una única bandera booleana para indicar "fin de la lista". Esto logra una estructura más compacta a expensas de un factor de sobrecarga constante por operación. ^[1]

Operaciones

Fusionar

La fusión con un montón vacío devuelve el otro montón; de lo contrario, se devuelve un nuevo montón que tiene el mínimo de los dos elementos raíz como su elemento raíz y simplemente agrega el montón con la raíz más grande a la lista de submontones:

función meld(heap1, heap2: PairingHeap[Elem]) -> PairingHeap[Elem] si heap1 está vacío retorna heap2 elsif heap2 está vacío retorna heap1 elsif heap1.elem < heap2.elem retorna Heap(heap1.elem, heap2 :: heap1.subheaps) de lo contrario  retorna Heap(heap2.elem, heap1 :: heap2.subheaps)

Insertar

La forma más fácil de insertar un elemento en un montón es fusionar el montón con un nuevo montón que contenga solo este elemento y una lista vacía de submontones:

función insertar(elem: Elem, montón: PairingHeap[Elem]) -> PairingHeap[Elem] devolver meld(Heap(elem, []), montón)

Buscar-min

La función find-min simplemente devuelve el elemento raíz del montón:

función find-min(heap: PairingHeap[Elem]) -> Elem si el montón está vacío error  de lo contrario  devuelve heap.elem

Eliminar-min

La única operación fundamental no trivial es la eliminación del elemento mínimo del montón. Esto requiere realizar repetidas fusiones de sus elementos secundarios hasta que solo quede un árbol. La estrategia estándar primero fusiona los submontones en pares (este es el paso que le dio su nombre a esta estructura de datos) de izquierda a derecha y luego fusiona la lista resultante de montones de derecha a izquierda:

función delete-min(heap: PairingHeap[Elem]) -> PairingHeap[Elem] si el montón está vacío error  de lo contrario  devolver merge-pairs(heap.subheaps)

Esto utiliza la función auxiliar merge-pairs :

función merge-pairs(lista: List[PairingTree[Elem]]) -> PairingHeap[Elem] si length(lista) == 0 devuelve Vacío elsif length(lista) == 1 devuelve lista[0] de lo contrario  devuelve meld(meld(lista[0], lista[1]), merge-pairs(lista[2..]))

Que esto realmente implementa la estrategia de fusión de dos pasadas de izquierda a derecha y luego de derecha a izquierda descrita se puede ver en esta reducción:

 pares de fusión ([H1, H2, H3, H4, H5, H6, H7])=> fusionar(fusionar(H1, H2), pares de fusión([H3, H4, H5, H6, H7])) # fusiona H1 y H2 con H12, luego el resto de la lista=> fusionar( H12 , fusionar(fusionar(H3, H4), pares de fusión([H5, H6, H7]))) # fusiona H3 y H4 con H34, luego el resto de la lista=> fusionar(H12, fusionar( H34 , fusionar(fusionar(H5, H6), fusionar pares([H7])))) # fusiona H5 y H6 con H56, luego el resto de la lista=> fusionar(H12, fusionar(H34, fusionar( H56 , H7))) # cambia la dirección, fusiona los dos últimos montones resultantes, dando como resultado H567=> fusionar(H12, fusionar(H34, H567 )) # fusiona los dos últimos montones resultantes, dando como resultado H34567=> fusionar(H12, H34567 ) # Finalmente, fusiona el primer par con el resultado de fusionar el resto.=> H1234567

Resumen de tiempos de ejecución

Aquí se muestran las complejidades temporales ^[12] de varias estructuras de datos de montón. La abreviatura am. indica que la complejidad dada se amortiza, de lo contrario es una complejidad del peor caso. Para el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones suponen un montón mínimo.

1. make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar en Θ ( n ) tiempo siempre que meld se ejecute en O (log  n ) tiempo (donde ambas complejidades se pueden amortizar). ^{[13] [14]} Otro algoritmo logra Θ ( n ) para montones binarios. ^[15]
2. Para los montículos persistentes (que no admiten decrease-key ), una transformación genérica reduce el costo de meld al de insert , mientras que el nuevo costo de delete-min es la suma de los costos anteriores de delete-min y meld . ^[18] Aquí, hace que meld se ejecute en Θ (1) tiempo (amortizado, si el costo de insert es) mientras que delete-min todavía se ejecuta en O (log  n ). Aplicado a montículos binomiales sesgados, produce colas Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos. ^[17]
3. Límite inferior de ^[20] límite superior de ^[21] ${\displaystyle \Omega (\log \log n),}$ ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$
4. colas de Brodal y los montículos de Fibonacci estrictos logran complejidades óptimas en el peor de los casos para los montículos. Primero se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que logra el mismo óptimo, excepto que no se admite la clave de disminución .

Referencias

1. Fredman, Michael L. ; Sedgewick, Robert ; Sleator, Daniel D. ; Tarjan, Robert E. (1986). "El montón de emparejamiento: una nueva forma de montón autoajustable" (PDF) . Algorithmica . 1 (1–4): 111–129. doi :10.1007/BF01840439. S2CID  23664143.
2. Mehlhorn, Kurt ; Sanders, Peter (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Springer. pág. 231.
3. Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Apuntes de clase en informática, vol. 1851, Springer-Verlag, págs. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi :10.1007/3-540-44985-X_5, ISBN  3-540-67690-2
4. Stasko, John T. ; Vitter, Jeffrey S. (1987), "Montones de emparejamiento: experimentos y análisis" (PDF) , Communications of the ACM , 30 (3): 234–249, CiteSeerX 10.1.1.106.2988 , doi :10.1145/214748.214759, S2CID  17811811 
5. Fredman, Michael L. (1999). "Sobre la eficiencia de emparejar montones y estructuras de datos relacionadas" (PDF) . Journal of the ACM . 46 (4): 473–501. doi :10.1145/320211.320214. S2CID  16115266. Archivado desde el original (PDF) el 2011-07-21 . Consultado el 2011-05-03 .
6. Pettie, Seth (2005), "Hacia un análisis final de los montones de emparejamiento" (PDF) , Proc. 46.º Simposio anual IEEE sobre fundamentos de la informática (PDF) , págs. 174-183, doi :10.1109/SFCS.2005.75, ISBN 0-7695-2468-0, Número de identificación del sujeto  2717102
7. Elmasry, Amr (2009), "El emparejamiento de montones con O(log log n) reduce el coste" (PDF) , Proc. 20.º Simposio anual ACM-SIAM sobre algoritmos discretos , págs. 471–476, CiteSeerX 10.1.1.502.6706 , doi :10.1137/1.9781611973068.52 
8. Elmasry, Amr (noviembre de 2017). "Hacia montones autoajustables óptimos". ACM Transactions on Algorithms . 13 (4): 1–14. doi :10.1145/3147138. S2CID  1182235.
9. Jones, Douglas W. (1986). "Una comparación empírica de implementaciones de colas de prioridad y conjuntos de eventos". Comunicaciones de la ACM . 29 (4): 300–311. CiteSeerX 10.1.1.117.9380 . doi :10.1145/5684.5686. S2CID  43650389. 
10. Larkin, Daniel H.; Sen, Siddhartha; Tarjan, Robert E. (2014), "Un estudio empírico de vuelta a lo básico de las colas de prioridad", Actas del 16.º Taller sobre ingeniería de algoritmos y experimentos , págs. 61-72, arXiv : 1403.0252 , doi : 10.1137/1.9781611973198.7, ISBN 978-1-61197-319-8, Número de identificación del sujeto  15216766
11. Chen, Mo; Chowdhury, Rezaul Alam; Ramachandran, Vijaya; Roche, David Lan; Tong, Lingling (12 de octubre de 2007). Colas prioritarias y algoritmo de Dijkstra (PDF) (Informe técnico). Universidad de Texas. TR-07-54.{{cite tech report}}: Mantenimiento CS1: fecha y año ( enlace )
12. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.
13. Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montones autoajustables". Revista SIAM de informática . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN  0097-5397. 
14. Tarjan, Robert (1983). "3.3. Montones de izquierdas". Estructuras de datos y algoritmos de red . págs. 38-42. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
15. Hayward, Ryan; McDiarmid, Colin (1991). "Análisis de caso promedio de construcción de montículos mediante inserción repetida" (PDF) . J. Algorithms . 12 : 126–153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Archivado desde el original (PDF) el 2016-02-05 . Consultado el 2016-01-28 . 
16. "Pila binomial | Wiki de matemáticas y ciencias brillante". brilliant.org . Consultado el 30 de septiembre de 2019 .
17. Brodal, Gerth Stølting; Okasaki, Chris (noviembre de 1996), "Colas de prioridad puramente funcionales óptimas", Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
18. Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). pp. 158-162. ISBN 9780521631242.
19. Takaoka, Tadao (1999), Teoría de 2-3 montones (PDF) , pág. 12
20. Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de emparejar montones y estructuras de datos relacionadas" (PDF) . Revista de la Asociación de Maquinaria Computacional . 46 (4): 473–501. doi :10.1145/320211.320214.
21. Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF) . FOCS '05 Actas del 46.º Simposio anual IEEE sobre fundamentos de la informática. pp. 174–183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN .  0-7695-2468-0.
22. Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Informática . 40 (6): 1463–1485. doi :10.1137/100785351.
23. Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Revista de la Asociación de Maquinaria Computacional . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874. 
24. Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones de Fibonacci estrictos (PDF) . Actas del 44.º simposio sobre teoría de la computación - STOC '12. págs. 1177–1184. CiteSeerX 10.1.1.233.1740 . doi :10.1145/2213977.2214082. ISBN  978-1-4503-1245-5.
25. Brodal, Gerth S. (1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Actas del 7.º Simposio anual ACM-SIAM sobre algoritmos discretos , págs. 52-58
26. Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montículos ascendentes". Estructuras de datos y algoritmos en Java (3.ª ed.). págs. 338–341. ISBN 0-471-46983-1.

Enlaces externos

• Louis Wasserman analiza los montones de emparejamiento y su implementación en Haskell en The Monad Reader, número 16 (págs. 37-52).
• emparejamiento de montones, Sartaj Sahni