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 práctico amortizado , presentado por Michael Fredman , Robert Sedgewick , Daniel Sleator y Robert Tarjan en 1986. [1] Los montones de emparejamiento son estructuras de árbol de múltiples vías ordenadas por montones , y pueden considerarse montones de Fibonacci simplificados . Se consideran una "opción sólida" para implementar algoritmos como el algoritmo MST de Prim , [2] y admiten las siguientes operaciones (asumiendo un min-heap):
- 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 agrega como hijo de esta raíz.
- insertar : crea un nuevo montón para el elemento insertado y fusiona en el montón original.
- disminución de clave (opcional): elimine el subárbol arraigado en la clave que se va a disminuir, reemplace la clave con una clave más pequeña y luego vuelva a combinar el resultado en el montón.
- delete-min : quita la raíz y haz combinaciones repetidas de sus subárboles hasta que quede un árbol. Se emplean varias estrategias de fusión.
Emparejamiento de montón | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | montón | ||||||||||||||||||||||||
Inventado | 1986 | ||||||||||||||||||||||||
Inventado por | Michael L. Fredman, Robert Sedgewick, Daniel Sleator y Robert Endre Tarjan | ||||||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||||||
|
El análisis de la complejidad temporal de los montones de emparejamiento se inspiró inicialmente en el de los árboles de extensión . [1] El tiempo amortizado por eliminación-min es O (log n ) , y las operaciones find-min , fusionar e insertar se ejecutan en O (1) tiempo amortizado. [3]
Cuando también se agrega una operación de tecla de disminución, resulta difícil determinar el tiempo de ejecución asintótico preciso de los montones de emparejamiento. Inicialmente, se conjeturaba empíricamente que la complejidad temporal de esta operación era O (1) , [4] pero Fredman demostró que el tiempo amortizado por clave de disminución es al menospara algunas secuencias de operaciones. [5] Usando un argumento de amortización diferente, Pettie luego demostró que insertar , fusionar y disminuir la clave se ejecutan en tiempo amortizado, que es . [6] Más tarde, Elmasry introdujo elaboraciones de montones de emparejamiento (lazy, consolidate) para los que se ejecuta la teclael tiempo amortizado y otras operaciones tienen límites amortizados óptimos, [7] [8] pero no ajustadosbound es conocido por la estructura de datos original. [3] [6]
Aunque el rendimiento asintótico de los montones de emparejamiento es peor que el de otros algoritmos de cola de prioridad, como los montones de Fibonacci , que realizan una clave de disminución entiempo amortizado, el rendimiento en la práctica es excelente. Jones [9] y Larkin, Sen y Tarjan [10] realizaron experimentos sobre emparejamiento de montones y otras estructuras de datos de montones. Llegaron a la conclusión de que los montones diarios , como los montones binarios, son más rápidos que todas las demás implementaciones de montones cuando no se necesita la operación de disminución de clave (y, por lo tanto, no es necesario realizar un seguimiento externo de la ubicación de los nodos en el montón), pero cuando disminuyen -Se necesita una clave Los montones de emparejamiento son a menudo más rápidos que los montones diarios y casi siempre más rápidos que otros montones basados en punteros, incluidas estructuras de datos como los montones de Fibonacci que son teóricamente más eficientes. Chen y col. [11] examinó las colas de prioridad específicamente para su uso con el algoritmo de Dijkstra y concluyó que, en casos normales, el uso de un montón d-ary sin clave de disminución (en lugar de duplicar nodos en el montón e ignorar las instancias redundantes) resultó en un mejor rendimiento, a pesar del rendimiento teórico inferior Garantías.
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 propio nodo. La siguiente descripción asume un montón puramente funcional que no admite la operación de disminución de clave .
tipo PairingTree [Elem] = Montón (elem: Elem, submontones: Lista [PairingTree [Elem]]) tipo PairingHeap [Elem] = Vacío | PairingTree [Elem]
Se puede lograr una implementación basada en punteros para máquinas RAM , que admita la tecla de disminución , utilizando tres punteros por nodo, al representar a los hijos de un nodo mediante una lista enlazada individualmente : un puntero al primer hijo del nodo, uno al siguiente hermano , y uno a su hermano anterior (o, para el hermano más a la izquierda, a su padre). Alternativamente, el puntero anterior se puede omitir dejando que el último hijo apunte al padre, si se agrega una sola bandera booleana para indicar "fin de lista". Esto logra una estructura más compacta a expensas de un factor de sobrecarga constante por operación. [1]
Operaciones
find-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
fusionar
La combinació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 elemento raíz y simplemente agrega el montón con la raíz más grande a la lista de submontones:
function meld (heap1, heap2: PairingHeap [Elem]) -> PairingHeap [Elem] si heap1 es Empty return heap2 elsif heap2 is Empty return heap1 elsif heap1.elemreturn Heap (heap1.elem, heap2 :: heap1. subheaps) else return 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, heap: PairingHeap [Elem]) -> PairingHeap [Elem] return meld (Heap (elem, []), heap)
eliminar min
La única operación fundamental no trivial es la eliminación del elemento mínimo del montón. Esto requiere realizar combinaciones repetidas de sus hijos hasta que solo quede un árbol. La estrategia estándar primero fusiona los submontones en pares (este es el paso que le dio a esta estructura de datos su nombre) 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 devuelve merge-pairs (heap.subheaps)
Esto usa la función auxiliar merge-pairs :
función merge-pairs (lista: Lista [PairingTree [Elem]]) -> PairingHeap [Elem] if length (list) == 0 return Empty elsif length (list) == 1 return list [0] else return meld (meld ( lista [0], lista [1]), pares de combinación (lista [2 ..]))
Que esto efectivamente 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 combinación ([H1, H2, H3, H4, H5, H6, H7])=> fusionar (fusionar (H1, H2), fusionar pares ([H3, H4, H5, H6, H7])) # fusionar H1 y H2 con H12, luego el resto de la lista=> fusionar ( H12 , fusionar (fusionar (H3, H4), fusionar pares ([H5, H6, H7]))) # fusionar H3 y H4 con H34, luego el resto de la lista=> fusionar (H12, fusionar ( H34 , fusionar (fusionar (H5, H6), fusionar pares ([H7])))) # fusionar H5 y H6 con H56, luego el resto de la lista=> fusionar (H12, fusionar (H34, fusionar ( H56 , H7))) # cambiar de dirección, fusionar los dos últimos montones resultantes, dando H567=> fusionar (H12, fusionar (H34, H567 )) # fusionar los dos últimos montones resultantes, dando H34567=> fusionar (H12, H34567 ) # finalmente, fusiona el primer par con el resultado de fusionar el resto=> H1234567
Resumen de tiempos de ejecución
Aquí están las complejidades de tiempo [12] de varias estructuras de datos de pila. Los nombres de las funciones asumen un min-heap. Para el significado de " O ( f )" y " Θ ( f )" ver Big O notación .
Operación | find-min | eliminar min | insertar | tecla de disminución | fusionar |
---|---|---|---|---|---|
Binario [12] | Θ (1) | Θ (log n ) | O (log n ) | O (log n ) | Θ ( n ) |
Izquierdista | Θ (1) | Θ (log n ) | Θ (log n ) | O (log n ) | Θ (log n ) |
Binomio [12] [13] | Θ (1) | Θ (log n ) | Θ (1) [a] | Θ (log n ) | O (log n ) [b] |
Fibonacci [12] [14] | Θ (1) | O (log n ) [a] | Θ (1) | Θ (1) [a] | Θ (1) |
Emparejamiento [3] | Θ (1) | O (log n ) [a] | Θ (1) | o (log n ) [a] [c] | Θ (1) |
Brodal [17] [d] | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
Emparejamiento de rango [19] | Θ (1) | O (log n ) [a] | Θ (1) | Θ (1) [a] | Θ (1) |
Fibonacci estricto [20] | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
2-3 montón [21] | O (log n ) | O (log n ) [a] | O (log n ) [a] | Θ (1) | ? |
- ^ a b c d e f g h i Tiempo amortizado.
- ^ n es el tamaño del montón más grande.
- ^ Límite inferior de[15] límite superior de[dieciséis]
- ^ Brodal y Okasaki describen más tarde unavariante persistente con los mismos límites, excepto para la tecla de disminución, que no es compatible. Los montones con n elementos se pueden construir de abajo hacia arriba en O ( n ). [18]
Referencias
- ↑ a b c 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) . Algoritmica . 1 (1–4): 111–129. doi : 10.1007 / BF01840439 . S2CID 23664143 .
- ^ Mehlhorn, Kurt ; Sanders, Peter (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Saltador. pag. 231.
- ^ a b c Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. Séptimo taller escandinavo sobre teoría de algoritmos (PDF) , Lecture Notes in Computer Science, 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
- ^ Stasko, John T .; Vitter, Jeffrey S. (1987), "Pairing montones: 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
- ^ Fredman, Michael L. (1999). "Sobre la eficiencia de emparejar montones y estructuras de datos relacionadas" (PDF) . Revista de la ACM . 46 (4): 473–501. doi : 10.1145 / 320211.320214 . S2CID 16115266 . Archivado desde el original (PDF) el 21 de julio de 2011 . Consultado el 3 de mayo de 2011 .
- ^ a b Pettie, Seth (2005), "Towards a final analysis of pairing montones" (PDF) , Proc. 46 ° Simposio anual del IEEE sobre los fundamentos de la informática (PDF) , págs. 174-183, doi : 10.1109 / SFCS.2005.75 , ISBN 0-7695-2468-0, S2CID 2717102
- ^ Elmasry, Amr (2009), "Emparejar montones con O (log log n ) disminuye el costo" (PDF) , Proc. 20o Simposio anual ACM-SIAM sobre algoritmos discretos , págs. 471–476, CiteSeerX 10.1.1.502.6706 , doi : 10.1137 / 1.9781611973068.52
- ^ Elmasry, Amr (noviembre de 2017). "Hacia montones óptimos autoajustables" . Transacciones ACM sobre algoritmos . 13 (4): 1–14. doi : 10.1145 / 3147138 . S2CID 1182235 .
- ^ Jones, Douglas W. (1986). "Una comparación empírica de implementaciones de cola de prioridad y conjunto de eventos". Comunicaciones de la ACM . 29 (4): 300–311. CiteSeerX 10.1.1.117.9380 . doi : 10.1145 / 5684.5686 . S2CID 43650389 .
- ^ Larkin, Daniel H .; Sen, Siddhartha; Tarjan, Robert E. (2014), "Un estudio empírico de vuelta a los fundamentos 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 , S2CID 15216766
- ^ Chen, Mo; Chowdhury, Rezaul Alam; Ramachandran, Vijaya; Roche, David Lan; Tong, Lingling (12 de octubre de 2007). Colas de prioridad y algoritmo de Dijkstra (PDF) (Informe técnico). Universidad de Texas. TR-07-54.Mantenimiento CS1: fecha y año ( enlace )
- ^ a b c d 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.
- ^ "Binomial Heap | Wiki brillante de matemáticas y ciencias" . shiny.org . Consultado el 30 de septiembre de 2019 .
- ^ Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montones de Fibonacci y sus usos en algoritmos de optimización de red mejorados" (PDF) . Revista de la Asociación de Maquinaria Informática . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145 / 28869.28874 .
- ^ 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 Informática . 46 (4): 473–501. doi : 10.1145 / 320211.320214 .
- ^ Pettie, Seth (2005). Hacia un análisis final de los montones de emparejamiento (PDF) . FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. págs. 174-183. CiteSeerX 10.1.1.549.471 . doi : 10.1109 / SFCS.2005.75 . ISBN 0-7695-2468-0.
- ^ Brodal, Gerth S. (1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Proc. Séptimo Simposio Anual ACM-SIAM sobre Algoritmos Discretos , págs. 52–58
- ^ Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montón de abajo hacia arriba". Estructuras de datos y algoritmos en Java (3ª ed.). págs. 338–341. ISBN 0-471-46983-1.
- ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Computación . 40 (6): 1463–1485. doi : 10.1137 / 100785351 .
- ^ Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones estrictos de Fibonacci (PDF) . Actas del 44º simposio de 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.
- ^ Takaoka, Tadao (1999), Teoría de 2-3 montones (PDF) , p. 12
enlaces externos
- Louis Wasserman analiza el emparejamiento de montones y su implementación en Haskell en The Monad Reader, número 16 (págs. 37-52).
- emparejamiento de montones , Sartaj Sahni