En informática , la cola Brodal es una estructura de cola de prioridad / montón con límites de tiempo muy bajos en el peor de los casos : para inserción, buscar mínimo, fusionar (fusionar dos colas) y disminuir clave y para eliminación mínima y eliminación general. Son la primera variante del montón en alcanzar estos límites sin recurrir a la amortización de los costos operativos. Las colas de Brodal llevan el nombre de su inventor Gerth Stølting Brodal . [1]
Aunque 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 Brodal. [2]
Resumen de tiempos de ejecución
Aquí están las complejidades de tiempo [3] 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 [3] | Θ (1) | Θ (log n ) | O (log n ) | O (log n ) | Θ ( n ) |
Izquierdista | Θ (1) | Θ (log n ) | Θ (log n ) | O (log n ) | Θ (log n ) |
Binomio [3] [4] | Θ (1) | Θ (log n ) | Θ (1) [a] | Θ (log n ) | O (log n ) [b] |
Fibonacci [3] [5] | Θ (1) | O (log n ) [a] | Θ (1) | Θ (1) [a] | Θ (1) |
Emparejamiento [6] | Θ (1) | O (log n ) [a] | Θ (1) | o (log n ) [a] [c] | Θ (1) |
Brodal [9] [d] | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
Emparejamiento de rango [11] | Θ (1) | O (log n ) [a] | Θ (1) | Θ (1) [a] | Θ (1) |
Fibonacci estricto [12] | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
2-3 montón [13] | 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[7] límite superior de[8]
- ^ 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 ). [10]
Referencias
- ↑ a b Gerth Stølting Brodal (1996). Colas de prioridad eficientes en el peor de los casos. Proc. 7 ° Simposio ACM-SIAM sobre algoritmos discretos, págs. 52–58
- ^ Gerth Stølting Brodal y Chris Okasaki (1996). Colas de prioridad óptimas puramente funcionales . Revista de programación funcional.
- ↑ 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 .
- ^ 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
- ^ 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