Cola de cubos

Una cola de cubos es una estructura de datos que implementa el tipo de datos abstracto de cola de prioridad : mantiene una colección dinámica de elementos con prioridades numéricas y permite un acceso rápido al elemento con prioridad mínima (o máxima). En la cola de cubos, las prioridades deben ser números enteros , y es particularmente adecuada para aplicaciones en las que las prioridades tienen un rango pequeño. ^[1] Una cola de cubos tiene la forma de una matriz de cubos: una estructura de datos de matriz , indexada por las prioridades, cuyas celdas contienen colecciones de elementos con la misma prioridad entre sí. Con esta estructura de datos, la inserción de elementos y los cambios de su prioridad toman un tiempo constante . La búsqueda y eliminación del elemento de prioridad mínima toma un tiempo proporcional al número de cubos o, al mantener un puntero al cubo encontrado más recientemente, en un tiempo proporcional a la diferencia de prioridades entre operaciones sucesivas.

La cola de cubos es el análogo de cola de prioridad del ordenamiento por casilleros (también llamado ordenamiento por cubos), un algoritmo de ordenamiento que coloca los elementos en cubos indexados por sus prioridades y luego concatena los cubos. El uso de una cola de cubos como cola de prioridad en un ordenamiento por selección proporciona una forma del algoritmo de ordenamiento por casilleros. ^[2] Las colas de cubos también se denominan colas de prioridad de cubos ^[3] o colas de prioridad de altura limitada . ^[1] Cuando se utilizan para aproximaciones cuantificadas a prioridades de números reales , también se denominan colas de prioridad desordenadas ^[4] o colas de pseudoprioridad . ^[5] Están estrechamente relacionadas con la cola de calendario , una estructura que utiliza una matriz similar de cubos para la priorización exacta por números reales.

Las aplicaciones de la cola de cubos incluyen el cálculo de la degeneración de un gráfico , algoritmos rápidos para rutas más cortas y rutas más anchas para gráficos con pesos que son enteros pequeños o que ya están ordenados, y algoritmos de aproximación voraz para el problema de cobertura de conjuntos . La versión cuantificada de la estructura también se ha aplicado a la programación ^[2] y a los cubos de marcha en gráficos de computadora . ^[4] El primer uso de la cola de cubos ^[6] fue en un algoritmo de ruta más corta de Dial (1969). ^[7]

Operación

Estructura de datos básica

Una cola de contenedores puede manejar elementos con prioridades enteras en el rango de 0 o 1 hasta algún límite conocido $C$ , y operaciones que insertan elementos, cambian la prioridad de elementos o extraen (buscan y eliminan) el elemento que tiene la prioridad mínima (o máxima). Consiste en una matriz $A$ de estructuras de datos de contenedor ; en la mayoría de las fuentes, estos contenedores son listas doblemente enlazadas , pero también podrían ser matrices dinámicas ^[3] o conjuntos dinámicos . El contenedor en la celda $p$ de la matriz $A [p]$ almacena la colección de elementos cuya prioridad es $p$ .

Una cola de depósitos puede gestionar las siguientes operaciones:

Para insertar un elemento $x$ con prioridad $p$ , agregue $x$ al contenedor en $A [p]$ .
Para cambiar la prioridad de un elemento, quítelo del contenedor de su prioridad anterior y vuelva a insertarlo en el contenedor de su nueva prioridad.
Para extraer un elemento con la prioridad mínima o máxima, realice una búsqueda secuencial en la matriz para encontrar el primer o el último contenedor no vacío, respectivamente, elija un elemento arbitrario de este contenedor y elimínelo del contenedor.

De esta manera, las inserciones y los cambios de prioridad toman un tiempo constante, y la extracción del elemento de prioridad mínima o máxima toma un tiempo $O (C)$ . ^[1]^[6]^[8]

Optimizaciones

Como optimización, la estructura de datos puede iniciar cada búsqueda secuencial de un contenedor no vacío en el contenedor no vacío encontrado más recientemente en lugar de al comienzo de la matriz. Esto se puede hacer de dos maneras diferentes, de forma perezosa (retrasando estas búsquedas secuenciales hasta que sean necesarias) o ansiosa (haciendo las búsquedas con anticipación). La elección de cuándo hacer la búsqueda afecta qué operaciones de la estructura de datos se ralentizan con estas búsquedas. La versión original de la estructura de Dial usaba una búsqueda perezosa. Esto se puede hacer manteniendo un índice $L$ que es un límite inferior en la prioridad mínima de cualquier elemento actualmente en la cola. Al insertar un nuevo elemento, $L$ debe actualizarse al mínimo de su valor anterior y la prioridad del nuevo elemento. Al buscar el elemento de prioridad mínima, la búsqueda puede comenzar en $L$ en lugar de en cero, y después de la búsqueda $L$ debe dejarse igual a la prioridad que se encontró en la búsqueda. ^[7]^[9] Alternativamente, la versión ansiosa de esta optimización mantiene $L$ actualizado para que siempre apunte al primer contenedor no vacío. Al insertar un nuevo elemento con una prioridad menor que $L$ , la estructura de datos establece $L$ en la nueva prioridad, y al eliminar el último elemento de un depósito con prioridad $L$ , realiza una búsqueda secuencial a través de índices mayores hasta encontrar un depósito no vacío y establece $L$ en la prioridad del depósito resultante. ^[1]

En cualquiera de estas dos variaciones, cada búsqueda secuencial toma un tiempo proporcional a la diferencia entre los valores antiguos y nuevos de $L$ . Esto podría ser significativamente más rápido que el límite de tiempo $O (C)$ para las búsquedas en la versión no optimizada de la estructura de datos. En muchas aplicaciones de colas de prioridad como el algoritmo de Dijkstra , las prioridades mínimas forman una secuencia monótona , lo que permite utilizar una cola de prioridad monótona . En estas aplicaciones, tanto para las variaciones perezosas como ansiosas de la estructura optimizada, las búsquedas secuenciales de contenedores no vacíos cubren rangos disjuntos de contenedores. Debido a que cada contenedor está en como máximo uno de estos rangos, sus números de pasos se suman como máximo $a C$ . Por lo tanto, en estas aplicaciones, el tiempo total para una secuencia de $n$ operaciones es $O (n + C)$ , en lugar del límite de tiempo $O (nC)$ más lento que resultaría sin esta optimización. ^[9] Se puede aplicar una optimización correspondiente en aplicaciones donde se utiliza una cola de contenedores para encontrar elementos de máxima prioridad, pero en este caso debe mantener un índice que limite superiormente la prioridad máxima, y la búsqueda secuencial de un contenedor no vacío debe proceder hacia abajo desde este límite superior. ^[10]

Otra optimización (ya dada por Dial 1969) puede utilizarse para ahorrar espacio cuando las prioridades son monótonas y, a lo largo de un algoritmo, siempre caen dentro de un rango de valores $r$ en lugar de extenderse sobre todo el rango de 0 a $C$ . En este caso, uno puede indexar la matriz por las prioridades módulo $r$ en lugar de por sus valores reales. La búsqueda del elemento de prioridad mínima siempre debe comenzar en el mínimo anterior, para evitar prioridades que sean más altas que el mínimo pero tengan módulos más bajos. En particular, esta idea puede aplicarse en el algoritmo de Dijkstra en grafos cuyas longitudes de aristas sean números enteros en el rango de 1 a $r$ . ^[8]

Como la creación de una nueva cola de contenedores implica inicializar una matriz de contenedores vacíos, este paso de inicialización lleva un tiempo proporcional al número de prioridades. Una variación de la cola de contenedores descrita por Donald B. Johnson en 1981 almacena en cambio solo los contenedores no vacíos en una lista enlazada, ordenados por sus prioridades, y utiliza un árbol de búsqueda auxiliar para encontrar rápidamente la posición en esta lista enlazada para cualquier contenedor nuevo. Se necesita tiempo $O (log log C)$ para inicializar esta estructura variante, tiempo constante para encontrar un elemento con prioridad mínima o máxima, y tiempo $O (log log D)$ para insertar o eliminar un elemento, donde $D$ es la diferencia entre las prioridades más pequeñas y más grandes más cercanas a la prioridad del elemento insertado o eliminado. ^[11]

Ejemplo

Por ejemplo, considere una cola de cubos con cuatro prioridades, los números 0, 1, 2 y 3. Consiste en una matriz cuyas cuatro celdas contienen cada una una colección de elementos, inicialmente vacía. Para los fines de este ejemplo, se puede escribir como una secuencia entre corchetes de cuatro conjuntos: . Considere una secuencia de operaciones en la que insertamos dos elementos y con la misma prioridad 1, insertamos un tercer elemento con prioridad 3, cambiamos la prioridad de a 3 y luego realizamos dos extracciones del elemento de prioridad mínima. ${\estilo de visualización A}$ ${\estilo de visualización A}$ $A=[\conjunto vacío ,\conjunto vacío ,\conjunto vacío ,\conjunto vacío ]$ ${\estilo de visualización x}$ ${\estilo de visualización y}$ ${\estilo de visualización z}$ ${\estilo de visualización x}$

Después de insertar con prioridad 1, . ${\estilo de visualización x}$ $A=[\conjunto vacío ,\{x\},\conjunto vacío ,\conjunto vacío ]$
Después de insertar con prioridad 1, . ${\estilo de visualización y}$ $A=[\conjunto vacío,\{x,y\},\conjunto vacío,\conjunto vacío]$
Después de insertar z con prioridad 3, . $A=[\conjunto vacío,\{x,y\},\conjunto vacío,\{z\}]$
Cambiar la prioridad de x de 1 a tres implica quitarlo de y agregarlo a , después de lo cual . $A[1]$ ${\estilo de visualización A[3]}$ $A=[\conjunto vacío,\{y\},\conjunto vacío,\{x,z\}]$
Al extraer el elemento de prioridad mínima, en la versión básica de la cola de buckets, se busca desde el inicio de para encontrar su primer elemento no vacío: está vacío pero , un conjunto no vacío. Elige un elemento arbitrario de este conjunto (el único elemento, ) como el elemento de prioridad mínima. Al eliminar de la estructura, queda . ${\estilo de visualización A}$ ${\estilo de visualización A[0]}$ $A[1]=\{y\}$ ${\estilo de visualización y}$ ${\estilo de visualización y}$ $A=[\conjunto vacío,\conjunto vacío,\conjunto vacío,\{x,z\}]$
La segunda operación de extracción, en la versión básica de la cola de cubos, busca nuevamente desde el inicio de la matriz: , , , no vacía. En las variantes mejoradas de la cola de cubos, esta búsqueda comienza en cambio en la última posición que se encontró que no estaba vacía, . En cualquier caso, se encuentra que es el primer conjunto no vacío. Uno de sus elementos se elige arbitrariamente como el elemento de prioridad mínima; por ejemplo, podría elegirse . Este elemento se elimina, dejando . $A[0]=\conjunto vacío$ $A[1]=\conjunto vacío$ $A[2]=\conjunto vacío$ $A[3]={}$ $A[1]$ $A[3]=\{x,z\}$ ${\estilo de visualización z}$ $A=[\conjunto vacío,\conjunto vacío,\conjunto vacío,\{x\}]$

Aplicaciones

Degeneración gráfica

Una cola de cubos se puede utilizar para mantener los vértices de un gráfico no dirigido , priorizados por sus grados , y encontrar y eliminar repetidamente el vértice de grado mínimo. ^[1] Este algoritmo voraz se puede utilizar para calcular la degeneración de un gráfico dado, igual al mayor grado de cualquier vértice en el momento de su eliminación. El algoritmo toma tiempo lineal , con o sin la optimización que mantiene un límite inferior en la prioridad mínima, porque cada vértice se encuentra en un tiempo proporcional a su grado y la suma de todos los grados de los vértices es lineal en el número de aristas del gráfico. ^[12]

Algoritmo de Dial para caminos más cortos

En el algoritmo de Dijkstra para caminos más cortos en grafos dirigidos con pesos de aristas que son enteros positivos, las prioridades son monótonas, ^[13] y una cola de cubos monótona se puede utilizar para obtener un límite de tiempo de $O (m + dc)$ , donde $m$ es el número de aristas, $d$ es el diámetro de la red y $c$ es el costo máximo (entero) del enlace. ^[9]^[14] Esta variante del algoritmo de Dijkstra también se conoce como algoritmo de Dial , ^[9] en honor a Robert B. Dial, quien lo publicó en 1969. ^[7] La misma idea también funciona, utilizando una cola de cubos cuantificada, para grafos con pesos de aristas reales positivos cuando la relación entre el peso máximo y el mínimo es como máximo $c$ . ^[15] En esta versión cuantificada del algoritmo, los vértices se procesan fuera de orden, en comparación con el resultado con una cola de prioridad no cuantificada, pero aún se encuentran los caminos más cortos correctos. ^[5] En estos algoritmos, las prioridades solo abarcarán un rango de ancho $c + 1$ , por lo que se puede utilizar la optimización modular para reducir el espacio a $O (n + c)$ . ^[8]^[14]

Se puede utilizar una variante del mismo algoritmo para el problema de la ruta más amplia . En combinación con métodos para dividir rápidamente los pesos de los bordes no enteros en subconjuntos a los que se les pueden asignar prioridades enteras, conduce a soluciones en tiempo casi lineal para la versión de origen único y destino único del problema de la ruta más amplia. ^[16]

Cubierta del conjunto Greedy

El problema de cobertura de conjuntos tiene como entrada una familia de conjuntos . La salida debe ser una subfamilia de estos conjuntos, con la misma unión que la familia original, incluyendo la menor cantidad posible de conjuntos. Es NP-hard , pero tiene un algoritmo de aproximación voraz que logra una relación de aproximación logarítmica, esencialmente la mejor posible a menos que P = NP . ^[17] Este algoritmo de aproximación selecciona su subfamilia eligiendo repetidamente un conjunto que cubra el número máximo posible de elementos restantes sin cubrir. ^[18] Un ejercicio estándar en el diseño de algoritmos pide una implementación de este algoritmo que tome tiempo lineal en el tamaño de entrada, que es la suma de los tamaños de todos los conjuntos de entrada. ^[19]

Esto puede resolverse utilizando una cola de conjuntos en la familia de entrada, priorizada por el número de elementos restantes que cubren. Cada vez que el algoritmo voraz elige un conjunto como parte de su salida, los elementos del conjunto recién cubiertos deben restarse de las prioridades de los otros conjuntos que los cubren; a lo largo del algoritmo, el número de estos cambios de prioridades es simplemente la suma de los tamaños de los conjuntos de entrada. Las prioridades son números enteros monótonamente decrecientes, limitados superiormente por el número de elementos a cubrir. Cada elección del algoritmo voraz implica encontrar el conjunto con la máxima prioridad, lo que puede hacerse escaneando hacia abajo a través de los conjuntos de la cola de conjuntos, comenzando desde el valor máximo anterior más reciente. El tiempo total es lineal en el tamaño de entrada. ^[10]

Programación

Las colas de contenedores se pueden utilizar para programar tareas con fechas límite, por ejemplo, en el reenvío de paquetes de datos de Internet con garantías de calidad de servicio . Para esta aplicación, las fechas límite se deben cuantificar en intervalos discretos y las tareas cuyas fechas límite caen en el mismo intervalo se consideran de prioridad equivalente. ^[2]

Una variación de la estructura de datos de cola de cubos cuantificados, la cola de calendario , se ha aplicado a la programación de simulaciones de eventos discretos , donde los elementos de la cola son eventos futuros priorizados por el momento dentro de la simulación en que deberían suceder los eventos. En esta aplicación, el orden de los eventos es crítico, por lo que las prioridades no se pueden aproximar. Por lo tanto, la cola de calendario realiza búsquedas del elemento de prioridad mínima de una manera diferente a una cola de cubos: en la cola de cubos, se puede devolver cualquier elemento del primer cubo no vacío, pero en su lugar la cola de calendario busca todos los elementos de ese cubo para determinar cuál de ellos tiene la prioridad no cuantificada más pequeña. Para mantener estas búsquedas rápidas, esta variación intenta mantener la cantidad de cubos proporcional a la cantidad de elementos, ajustando la escala de cuantificación y reconstruyendo la estructura de datos cuando se desequilibra. Las colas de calendario pueden ser más lentas que las colas de contenedores en el peor de los casos (cuando muchos elementos terminan en el mismo contenedor más pequeño), pero son rápidas cuando los elementos se distribuyen uniformemente entre los contenedores, lo que hace que el tamaño promedio del contenedor sea constante. ^[20]^[21]

Marcha rápida

En matemáticas aplicadas y métodos numéricos para la solución de ecuaciones diferenciales , se han utilizado colas de prioridad desordenadas para priorizar los pasos del método de marcha rápida para resolver problemas de valores de contorno de la ecuación de Eikonal , utilizada para modelar la propagación de ondas . Este método encuentra los tiempos en los que un límite en movimiento cruza un conjunto de puntos discretos (como los puntos de una cuadrícula de números enteros) utilizando un método de priorización que se asemeja a una versión continua del algoritmo de Dijkstra , y su tiempo de ejecución está dominado por su cola de prioridad de estos puntos. Se puede acelerar a tiempo lineal redondeando las prioridades utilizadas en este algoritmo a números enteros y utilizando una cola de cubos para estos números enteros. Al igual que en los algoritmos de Dijkstra y Dial, las prioridades son monótonas, por lo que la marcha rápida puede utilizar la optimización monótona de la cola de cubos y su análisis. Sin embargo, la discretización introduce algún error en los cálculos resultantes. ^[4]

Véase también

Montón blando , una forma diferente de acelerar las colas de prioridad mediante el uso de prioridades aproximadas

Referencias

^ abcde Skiena, Steven S. (1998), Manual de diseño de algoritmos, Springer, pág. 181, ISBN 9780387948607.
^ abc Figueira, NR (1997), "Una solución para el problema de la cola de prioridad de las disciplinas de servicio ordenadas por fecha límite", Actas de la Sexta Conferencia Internacional sobre Comunicaciones y Redes Informáticas , IEEE Computer Society Press, pp. 320–325, doi :10.1109/icccn.1997.623330, S2CID 5611516
^ ab Henzinger, Monika ; Noe, Alexander; Schulz, Christian (2019), "Shared-memory exact minimum cuts", Simposio internacional IEEE de procesamiento paralelo y distribuido de 2019, IPDPS 2019, Río de Janeiro, Brasil, 20-24 de mayo de 2019 , págs. 13-22, arXiv : 1808.05458 , doi :10.1109/IPDPS.2019.00013, S2CID 52019258
^ abc Rasch, cristiano; Satzger, Thomas (2009), "Observaciones sobre la implementación O(N) del método de marcha rápida" (PDF) , IMA Journal of Numerical Analysis , 29 (3): 806–813, doi :10.1093/imanum/drm028, MR 2520171
^ ab Robledo, Alicia; Guivant, José E. (2010), "Colas de pseudoprioridad para el rendimiento en tiempo real en procesos de programación dinámica aplicados a la planificación de rutas" (PDF) , en Wyeth, Gordon; Upcroft, Ben (eds.), Conferencia Australasiana sobre Robótica y Automatización
^ ab Edelkamp, Stefan; Schroedl, Stefan (2011), "3.1.1 Estructuras de datos de contenedores", Búsqueda heurística: teoría y aplicaciones , Elsevier, págs. 90-92, ISBN 9780080919737. Véase también la página 157 para conocer la historia y el nombre de esta estructura.
^ abc Dial, Robert B. (1969), "Algoritmo 360: Bosque de caminos más cortos con ordenamiento topológico [H]", Communications of the ACM , 12 (11): 632–633, doi : 10.1145/363269.363610 , S2CID 6754003.
^ abc Mehlhorn, Kurt ; Sanders, Peter (2008), "10.5.1 Colas de contenedores", Algoritmos y estructuras de datos: la caja de herramientas básica , Springer, pág. 201, ISBN 9783540779773.
^ abcd Bertsekas, Dimitri P. (1991), "Algoritmo de Dial", Optimización de redes lineales: algoritmos y códigos , Cambridge, Massachusetts: MIT Press, págs. 72–75, ISBN 0-262-02334-2, Sr. 1201582
^ ab Lim, CL; Moffat, Alistair; Wirth, Anthony Ian (2014), "Enfoques perezosos y ansiosos para el problema de la cobertura de conjuntos", en Thomas, Bruce; Parry, Dave (eds.), Trigésima séptima Conferencia de Ciencias de la Computación de Australasia, ACSC 2014, Auckland, Nueva Zelanda, enero de 2014 , CRPIT, vol. 147, Australian Computer Society, págs. 19–27Véase en particular la sección 2.4, "Cola de prioridad", pág. 22.
^ Johnson, Donald B. (1981), "Una cola de prioridad en la que las operaciones de inicialización y de cola toman un tiempo $O$ $(log log$ $D$ $)$ ", Mathematical Systems Theory , 15 (4): 295–309, doi :10.1007/BF01786986, MR 0683047, S2CID 35703411
^ Matula, David W .; Beck, LL (1983), "Algoritmos de ordenamiento y agrupamiento y coloración de grafos de menor a mayor", Journal of the ACM , 30 (3): 417–427, doi : 10.1145/2402.322385 , MR 0709826, S2CID 4417741.
^ Varghese, George (2005), Algoritmos de red: un enfoque interdisciplinario para diseñar dispositivos en red rápidos, Morgan Kaufmann, págs. 78-80, ISBN 9780120884773.
^ ab Festa, Paola (2006), "Algoritmos de ruta más corta", en Resende, Mauricio GC ; Pardalos, Panos M. (eds.), Handbook of Optimization in Telecommunications , Boston: Springer, pp. 185–210, doi :10.1007/978-0-387-30165-5_8; ver en particular la Sección 8.3.3.6, "Implementación de Dial", págs. 194-195.
^ Mehlhorn y Sanders (2008) (Ejercicio 10.11, p. 201) atribuyen esta idea a un artículo de 1978 de EA Dinic (Yefim Dinitz).
^ Gabow, Harold N. ; Tarjan, Robert E. (1988), "Algoritmos para dos problemas de optimización de cuello de botella", Journal of Algorithms , 9 (3): 411–417, doi :10.1016/0196-6774(88)90031-4, MR 0955149
^ Dinur, Irit ; Steurer, David (2014), "Enfoque analítico para la repetición paralela", en Shmoys, David B. (ed.), Simposio sobre teoría de la computación, STOC 2014, Nueva York, NY, EE. UU., 31 de mayo - 3 de junio de 2014 , ACM, págs. 624–633, arXiv : 1305.1979 , doi : 10.1145/2591796.2591884, MR 3238990, S2CID 15252482
^ Johnson, David S. (1974), "Algoritmos de aproximación para problemas combinatorios", Journal of Computer and System Sciences , 9 (3): 256–278, doi :10.1016/S0022-0000(74)80044-9, MR 0449012
^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990], "Ejercicio 35.3-3", Introducción a los algoritmos (3.ª ed.), MIT Press y McGraw-Hill, p. 1122, ISBN 0-262-03384-4
^ Brown, R. (octubre de 1988), "Colas de calendario: una implementación rápida de colas de prioridad para el problema de conjunto de eventos de simulación", Communications of the ACM , 31 (10): 1220–1227, doi : 10.1145/63039.63045 , S2CID 32086497 ${\estilo de visualización O(1)}$
^ Erickson, K. Bruce; Ladner, Richard E .; LaMarca, Anthony (2000), "Optimización de colas de calendario estático", ACM Transactions on Modeling and Computer Simulation , 10 (3): 179–214, doi : 10.1145/361026.361028