En informática , una cola de prioridad monótona es una variante del tipo de datos abstractos de cola de prioridad en la que se requieren las prioridades de los elementos extraídos para formar una secuencia monótona . Es decir, para una cola de prioridad en la que cada elemento extraído sucesivamente es el que tiene la prioridad mínima (un montón mínimo), la prioridad mínima debe aumentar monótonamente. A la inversa, para un montón máximo, la prioridad máxima debería ser monótonamente decreciente. La suposición de monotonicidad surge naturalmente en varias aplicaciones de colas de prioridad y se puede utilizar como una suposición simplificadora para acelerar ciertos tipos de colas de prioridad. [1] : 128
Una condición necesaria y suficiente en una cola de prioridad monótona es que uno nunca intente agregar un elemento con menor prioridad que el extraído más recientemente.
Aplicaciones [ editar ]
Las colas de prioridad monótona surgen naturalmente cuando se organizan eventos en orden de tiempo, como tiempos de espera de red o simulación de eventos discretos . Un evento puede hacer que alguna acción se programe en algún momento en el futuro, pero la causalidad (real o simulada) hace que los intentos de programar acciones en el pasado carezcan de sentido.
En el algoritmo de Dijkstra para el problema de la ruta más corta , los vértices de un gráfico ponderado dado se extraen en orden creciente por su distancia desde el vértice inicial, y se usa una cola de prioridad para determinar el vértice restante más cercano al vértice inicial. Por lo tanto, en esta aplicación, las operaciones de cola de prioridad son monótonas.
De manera similar, en los algoritmos de línea de barrido en geometría computacional , los eventos en los que la línea de barrido cruza un punto de interés se priorizan por la coordenada del punto cruzado, y estos eventos se extraen en un orden monótono. También se produce un orden de extracción monótono en la mejor primera versión de branch and bound . [1] : 128
Estructuras de datos [ editar ]
Cualquier cola de prioridad que pueda manejar operaciones de extracción no monótona también puede manejar extracciones monótonas, pero algunas colas de prioridad están especializadas para funcionar solo para extracciones monótonas o funcionan mejor cuando las extracciones son monótonas. Por ejemplo, la cola de cubo es una estructura de datos de cola de prioridad simple que consiste en una matriz indexada por prioridad, donde cada celda de la matriz contiene una cubeta de artículos con esa prioridad. Una operación de extracción mínima realiza una búsqueda secuencialpara el primer depósito no vacío y elige un elemento arbitrario en ese depósito. Para extracciones no monótonas, cada operación extract-min lleva un tiempo (en el peor de los casos) proporcional a la longitud de la matriz (el número de prioridades distintas). Sin embargo, cuando se usa como una cola de prioridad monótona, la búsqueda del siguiente depósito no vacío puede comenzar en la prioridad de la operación extract-min anterior más reciente en lugar de al comienzo de la matriz. Esta optimización hace que el tiempo total para una secuencia de operaciones sea proporcional a la suma del número de operaciones y la longitud de la matriz, en lugar de (como en el caso no monótono) el producto de estas dos cantidades. [2]
Cherkassky, Goldberg y Silverstein (1999) describen un esquema más complicado llamado cola Heap-on-top (HOT) para colas de prioridad monótona con prioridades enteras, basado en agrupamiento multinivel junto con una cola de prioridad de montón convencional. Usando este método que obtienen una estructura que puede mantener los artículos con las prioridades de número entero en un intervalo desde 0 a un parámetro C . La cola caliente utiliza un tiempo constante por inserción o operación con prioridad decreciente y un tiempo amortizado por operación de extracción por minuto. [3] Otra estructura relacionada de Raman (1996)permite que las prioridades sean números enteros de la máquina y, nuevamente, permite operaciones de inserción y disminución de prioridad en tiempo constante, con operaciones de extracción mínima en una cola de prioridad de n elementos que toman tiempo amortizado . [4] Estos resultados conducen a una aceleración correspondiente en el algoritmo de Dijkstra para gráficos con pesos de bordes enteros.
Referencias [ editar ]
- ^ a b Mehlhorn, Kurt ; Sanders, Peter (2008). "Colas de prioridad" (PDF) . Algoritmos y estructuras de datos: la caja de herramientas básica . Saltador.
- ^ Skiena, Steven S. (1998), El manual de diseño de algoritmos , Springer, p. 181, ISBN 978-0-387-94860-7 CS1 maint: parámetro desalentado ( enlace ).
- ^ Cherkassky, Boris V .; Goldberg, Andrew V .; Silverstein, Craig (agosto de 1999), "Buckets, montones, listas y colas de prioridad monótona", SIAM Journal on Computing , 28 (4): 1326–1346 (electrónico), CiteSeerX 10.1.1.49.8244 , doi : 10.1137 / S0097539796313490 , MR 1681014 .
- ^ Raman, Rajeev (1996), "Colas de prioridad: pequeñas, monótonas y trans-dicotómicas" (PDF) , Algoritmos — ESA '96 (Barcelona) , Lecture Notes in Computer Science, 1136 , Berlín: Springer, págs. 121-137 , doi : 10.1007 / 3-540-61680-2_51 , MR 1469229 .
