En informática , una cola de prioridad monótona es una variante del tipo de datos abstracto de cola de prioridad en la que se requiere que las prioridades de los elementos extraídos formen 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 min-heap), la prioridad mínima debería aumentar de forma monótona. Por el contrario, para un max-heap, la prioridad máxima debería disminuir de forma monótona. El supuesto de monotonía surge de forma natural en varias aplicaciones de colas de prioridad y se puede utilizar como un supuesto simplificador 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.
Las colas de prioridad monótonas surgen de manera natural cuando se organizan eventos en orden de tiempo, como tiempos de espera de red o simulaciones de eventos discretos . Un evento puede hacer que se programe alguna acción 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 grafo ponderado dado se extraen en orden creciente según su distancia desde el vértice inicial, y se utiliza 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 la 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 según la coordenada del punto cruzado, y estos eventos se extraen en orden monótono. Un orden de extracción monótono también ocurre en la versión de mejor primero de ramificación y límite . [1] : 128
Cualquier cola de prioridad que pueda manejar operaciones de extracción no monótonas 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 cubos 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 un cubo de elementos con esa prioridad. Una operación extract-min realiza una búsqueda secuencial del primer cubo no vacío y elige un elemento arbitrario en ese cubo. Para extracciones no monótonas, cada operación extract-min lleva tiempo (en el peor de los casos) proporcional a la longitud de la matriz (la cantidad de prioridades distintas). Sin embargo, cuando se usa como una cola de prioridad monótona, la búsqueda del siguiente cubo 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 de la cantidad 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 heap convencional. Usando este método obtienen una estructura que puede mantener elementos con prioridades enteras en un rango de 0 a un parámetro C . La cola caliente usa tiempo constante por operación de inserción o disminución de prioridad y tiempo amortizado por operación de extracción mínima. [3] Otra estructura relacionada de Raman (1996) permite que las prioridades sean números enteros de máquina, y nuevamente permite operaciones de inserción y disminución de prioridad de 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 borde enteros.
