Cola de Brodal

Estructura de datos óptima para operaciones de cola de prioridad

En informática , la cola Brodal es una estructura de cola de prioridad / montón con límites de tiempo muy bajos para el peor de los casos : para inserción, búsqueda mínima, fusión (fusión de dos colas) y disminución de clave, y para eliminación mínima y eliminación general. Son la primera variante de montón que logra estos límites sin recurrir a la amortización de los costos operativos. Las colas Brodal reciben su nombre de su inventor, Gerth Stølting Brodal . ^[1] ${\displaystyle O(1)}$ ${\displaystyle O(\mathrm {log} (n))}$

Si bien tienen mejores límites asintóticos que otras estructuras de colas de prioridad, son, en palabras del propio Brodal, "bastante complicadas" y "[no] aplicables en la práctica". ^[1] Brodal y Okasaki describen una versión persistente ( puramente funcional ) de las colas de Brodal. ^[2]

Resumen de los tiempos de ejecución

Aquí se muestran las complejidades temporales ^[3] 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). ^{[4] [5]} Otro algoritmo logra Θ ( n ) para montones binarios. ^[6]
2. Para los montículos persistentes (que no admiten la función 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 . ^[9] Aquí, hace que meld se ejecute en Θ (1) tiempo (amortizado, si el costo de insert es) mientras que delete-min aún se ejecuta en O (log  n ). Aplicado a montículos binomiales sesgados, produce colas de Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos. ^[8]
3. Límite inferior de ^[12] límite superior de ^[13] ${\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. Gerth Stølting Brodal (1996). Colas de prioridad eficientes en el peor de los casos. Actas del 7.º Simposio ACM-SIAM sobre algoritmos discretos, págs. 52-58
2. Gerth Stølting Brodal y Chris Okasaki (1996). Colas de prioridad puramente funcionales óptimas. Journal of Functional Programming.
3. 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.
4. 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. 
5. 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.
6. 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 . 
7. "Pila binomial | Wiki de matemáticas y ciencias brillante". brilliant.org . Consultado el 30 de septiembre de 2019 .
8. 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
9. Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). pp. 158-162. ISBN 9780521631242.
10. Takaoka, Tadao (1999), Teoría de 2-3 montones (PDF) , pág. 12
11. 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
12. 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.
13. 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.
14. 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.
15. 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. 
16. 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.
17. 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
18. 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.