Cola de prioridad

Se puede crear una cola de prioridad simple, aunque ineficiente, de varias maneras. Estas implementaciones sencillas permiten demostrar el comportamiento esperado de una cola de prioridad de forma más simple.

• insertar elementos en un array no ordenado; encontrar y extraer el elemento con mayor prioridad.

  Rendimiento: " insert" actúa en${\displaystyle O(1)}$tiempo constante, donde " extract_max" se desempeña en${\displaystyle O(n)}$tiempo lineal.

insertar (elemento, prioridad): nodo.elemento ← elemento nodo.prioridad ← prioridad lista.añadir(nodo) extraer_máximo (): más alto ← 0 para cada nodo en la lista: Si highest.priority < node.priority: más alto ← nodo lista.eliminar(más alto) devolver elemento más alto

• insertar elementos en un array ordenado; extraer el primer elemento

  Rendimiento: " insert" actúa en${\displaystyle O(n)}$tiempo lineal, donde " extract_max" se desempeña en${\displaystyle O(1)}$tiempo constante.

insertar (elemento, prioridad): nodo.elemento ← elemento nodo.prioridad ← prioridad para i en [0...N]: elemento ← lista.get_at_index(i) Si element.priority < node.priority: lista.insertar_en_índice(nodo, i + 1) devolver extraer_máximo (): más alto ← lista.get_at_index(0) lista.eliminar(más alto) devolver elemento más alto

Para mejorar el rendimiento, las colas de prioridad se basan normalmente en un montón , lo que da${\displaystyle O(\log n)}$rendimiento para inserciones y extracciones, y${\displaystyle O(n)}$construir el montón inicialmente a partir de un conjunto de${\displaystyle n}$elementos. Las variantes de la estructura de datos de montón básica, como los montones de emparejamiento o los montones de Fibonacci, pueden proporcionar mejores límites para algunas operaciones. ^{[ 6 ]}

Alternativamente, cuando se utiliza un árbol de búsqueda binaria autoequilibrado , la inserción y la eliminación también toman${\displaystyle O(\log n)}$tiempo, aunque construir árboles a partir de secuencias de elementos existentes lleva${\displaystyle O(n\log n)}$tiempo; esto es típico cuando ya se tiene acceso a estas estructuras de datos, como con bibliotecas estándar o de terceros. Desde el punto de vista de la complejidad espacial, usar un árbol de búsqueda binaria autoequilibrado con lista enlazada requiere más almacenamiento, ya que necesita almacenar referencias adicionales a otros nodos.

Desde el punto de vista de la complejidad computacional, las colas de prioridad son congruentes con los algoritmos de ordenación. La sección sobre la equivalencia entre colas de prioridad y algoritmos de ordenación , que se presenta a continuación, describe cómo los algoritmos de ordenación eficientes pueden generar colas de prioridad eficientes.

Existen varias estructuras de datos de montón especializadas que proporcionan operaciones adicionales o superan el rendimiento de las implementaciones basadas en montón para tipos específicos de claves, en concreto, claves enteras. Supongamos que el conjunto de claves posibles es${\displaystyle \{1,2,...,C\}}$.

• Cuando solo se necesitan insert, find-miny y en caso de prioridades enteras, se puede construir una cola de cubetas como una matriz deextract-min${\displaystyle C}$listas enlazadas más un puntero${\displaystyle {\text{superior}}}$, inicialmente${\displaystyle C}$Insertar un elemento con clave${\displaystyle k}$agrega el elemento a la${\displaystyle k}$Lista y actualizaciones${\displaystyle {\text{top}}\gets {\text{min}}({\text{top}},k)}$, ambos en tiempo constante. extract-minElimina y devuelve un elemento de la lista con índice${\displaystyle {\text{superior}}}$, luego incrementos${\displaystyle {\text{superior}}}$si es necesario hasta que vuelva a apuntar a una lista no vacía; esto toma${\displaystyle O(C)}$tiempo en el peor de los casos. Estas colas son útiles para ordenar los vértices de un grafo por su grado. ^{[ 7 ] : 374}
• Un árbol de van Emde Boas admite las operaciones minimum, maximum, insert, delete, search, extract-min, extract-max, predecessory ensuccessor]${\displaystyle O(\log \log C)}$tiempo, pero tiene un costo de espacio para colas pequeñas de aproximadamente${\displaystyle O(2^{m/2})}$, dónde${\displaystyle m}$es el número de bits en el valor de prioridad. ^{[ 8 ]} El espacio se puede reducir significativamente con el hashing.
• El árbol Fusion de Fredman y Willard implementa la minimumoperación en${\displaystyle O(1)}$tiempo y insertoperaciones extract-minen${\displaystyle O(\log n/\log \log C)}$tiempo. Sin embargo, el autor afirma que: «Nuestros algoritmos tienen interés meramente teórico; los factores constantes que influyen en los tiempos de ejecución impiden su aplicación práctica». ^{[ 9 ]}

Para aplicaciones que realizan muchas operaciones de " mirar " por cada extract-minoperación " ", la complejidad temporal de las acciones de mirar se puede reducir a${\displaystyle O(1)}$En todas las implementaciones de árbol y montón, se almacena en caché el elemento de mayor prioridad después de cada inserción y eliminación. Para la inserción, esto añade como máximo un coste constante, ya que el elemento recién insertado se compara únicamente con el elemento mínimo previamente almacenado en caché. Para la eliminación, esto añade como máximo un coste adicional de "inspección", que suele ser menor que el coste de eliminación, por lo que la complejidad temporal general no se ve afectada significativamente.

Las colas de prioridad monótonas son colas especializadas optimizadas para el caso en que nunca se inserta un elemento con una prioridad inferior (en el caso de un montículo mínimo) a la de cualquier elemento extraído previamente. Esta restricción se cumple en diversas aplicaciones prácticas de las colas de prioridad.

Aquí se muestran las complejidades temporales ^{[ 10 ]} de diversas estructuras de datos de montículo. La abreviatura am. indica que la complejidad dada está amortizada; de lo contrario, se trata de la complejidad en el peor de los casos. Para conocer el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones presuponen un montículo mínimo.

La semántica de las colas de prioridad sugiere naturalmente un método de ordenación: insertar todos los elementos a ordenar en una cola de prioridad y eliminarlos secuencialmente; aparecerán ordenados. Este es, de hecho, el procedimiento utilizado por varios algoritmos de ordenación , una vez eliminada la capa de abstracción que proporciona la cola de prioridad. Este método de ordenación es equivalente a los siguientes algoritmos de ordenación:

También se puede utilizar un algoritmo de ordenación para implementar una cola de prioridad. Específicamente, Thorup dice: ^{[ 26 ]}

Presentamos una reducción de espacio lineal determinista general de colas de prioridad a ordenación, lo que implica que si podemos ordenar hasta${\displaystyle n}$llaves en${\displaystyle S(n)}$tiempo por clave, luego hay una cola de prioridad que admite deletey inserten${\displaystyle O(S(n))}$tiempo y find-minen tiempo constante.

Es decir, si existe un algoritmo de ordenación que pueda ordenar en${\displaystyle O(S)}$tiempo por tecla, donde${\displaystyle S}$es alguna función de${\displaystyle n}$y tamaño de palabra , ^{[ 27 ]} entonces se puede utilizar el procedimiento dado para crear una cola de prioridad donde extraer el elemento de mayor prioridad es${\displaystyle O(1)}$tiempo, e insertar nuevos elementos (y eliminar elementos) es${\displaystyle O(S)}$tiempo. Por ejemplo, si uno tiene un${\displaystyle O(n\log n)}$algoritmo de ordenación, se puede crear una cola de prioridad con${\displaystyle O(1)}$tirando y${\displaystyle O(\log n)}$inserción.

La priorización de colas se puede utilizar para gestionar recursos limitados, como el ancho de banda en una línea de transmisión desde un enrutador de red . En caso de que el tráfico saliente se acumule en la cola debido a un ancho de banda insuficiente, todas las demás colas se pueden detener para enviar el tráfico de la cola de mayor prioridad al llegar. Esto garantiza que el tráfico prioritario (como el tráfico en tiempo real, por ejemplo, una transmisión RTP de una conexión VoIP ) se reenvíe con el menor retraso y la menor probabilidad de ser rechazado debido a que una cola alcance su capacidad máxima. El resto del tráfico se puede gestionar cuando la cola de mayor prioridad esté vacía. Otro enfoque utilizado consiste en enviar una cantidad desproporcionadamente mayor de tráfico desde las colas de mayor prioridad.

Muchos protocolos modernos para redes de área local también incluyen el concepto de colas de prioridad en la subcapa de control de acceso al medio (MAC) para garantizar que las aplicaciones de alta prioridad (como VoIP o IPTV ) experimenten una latencia menor que otras aplicaciones que pueden ser atendidas con un servicio de mejor esfuerzo . Algunos ejemplos incluyen IEEE 802.11e (una enmienda a IEEE 802.11 que proporciona calidad de servicio ) e ITU-T G.hn (un estándar para redes de área local de alta velocidad que utilizan el cableado doméstico existente ( líneas eléctricas , líneas telefónicas y cables coaxiales ).

Normalmente, se establece una limitación (policía) para restringir el ancho de banda que puede utilizar el tráfico de la cola de mayor prioridad, con el fin de evitar que los paquetes de alta prioridad saturen el resto del tráfico. Este límite rara vez se alcanza gracias a instancias de control de alto nivel, como Cisco Callmanager , que se puede programar para bloquear las llamadas que superen el límite de ancho de banda programado.

Otro uso de una cola de prioridad es gestionar los eventos en una simulación de eventos discretos . Los eventos se añaden a la cola utilizando su tiempo de simulación como criterio de prioridad. La ejecución de la simulación se lleva a cabo extrayendo repetidamente el elemento superior de la cola y ejecutando el evento correspondiente.

Véase también : Planificación (informática) , teoría de colas

Cuando el grafo se almacena en forma de lista de adyacencia o matriz, se puede utilizar una cola de prioridad para extraer el mínimo de manera eficiente al implementar el algoritmo de Dijkstra , aunque también se necesita la capacidad de modificar la prioridad de un vértice en particular en la cola de prioridad de manera eficiente.

Si, en cambio, un grafo se almacena como objetos de nodo y los pares prioridad-nodo se insertan en un montón, no es necesario modificar la prioridad de un vértice en particular si se realiza un seguimiento de los nodos visitados. Una vez visitado un nodo, si vuelve a aparecer en el montón (tras haber tenido un número de prioridad menor asociado anteriormente), se elimina y se ignora.

La codificación de Huffman requiere obtener repetidamente los dos árboles de menor frecuencia. Una cola de prioridad es un método para lograrlo .

Los algoritmos de búsqueda primero en amplitud , como el algoritmo A* , encuentran el camino más corto entre dos vértices o nodos de un grafo ponderado , probando primero las rutas más prometedoras. Se utiliza una cola de prioridad (también conocida como límite inferior ) para gestionar las rutas no exploradas; aquella cuya estimación (un límite inferior en el caso de A*) de la longitud total del camino sea la más pequeña recibe la máxima prioridad. Si las limitaciones de memoria hacen que la búsqueda primero en amplitud sea impracticable, se pueden utilizar variantes como el algoritmo SMA* , con una cola de prioridad de doble extremo para permitir la eliminación de elementos de baja prioridad.

El algoritmo ROAM (Real-time Optimally Adapting Meshes ) calcula una triangulación dinámica del terreno. Su funcionamiento se basa en dividir los triángulos donde se requiere mayor detalle y fusionarlos donde se requiere menor detalle. El algoritmo asigna a cada triángulo del terreno una prioridad, generalmente relacionada con la reducción del error que se produciría al dividirlo. El algoritmo utiliza dos colas de prioridad: una para los triángulos que se pueden dividir y otra para los que se pueden fusionar. En cada paso, se divide el triángulo de la cola de división con la prioridad más alta, o se fusiona con sus vecinos el triángulo de la cola de fusión con la prioridad más baja.

Al usar la cola de prioridad de montículo mínimo en el algoritmo de Prim para encontrar el árbol de expansión mínimo de un grafo conectado y no dirigido , se puede lograr un buen tiempo de ejecución. Esta cola de prioridad de montículo mínimo utiliza la estructura de datos de montículo mínimo que admite operaciones tales como , , , . ^{[ 28 ]} En esta implementación, el peso de las aristas se usa para decidir la prioridad de los vértices . Menor peso, mayor prioridad y mayor peso, menor prioridad. ^{[ 29 ]}insertminimumextract-mindecrease-key

Si la cola de prioridad permite el acceso concurrente, varios procesos pueden realizar operaciones simultáneamente en ella. Sin embargo, esto plantea dos problemas. En primer lugar, la definición de la semántica de las operaciones individuales deja de ser evidente. Por ejemplo, si dos procesos desean extraer el elemento con la prioridad más alta, ¿deberían obtener el mismo elemento o elementos diferentes? Esto restringe el paralelismo a nivel del programa que utiliza la cola de prioridad. Además, dado que varios procesos tienen acceso al mismo elemento, esto genera contención.

El acceso concurrente a una cola de prioridad se puede implementar en un modelo PRAM de lectura concurrente, escritura concurrente (CRCW). A continuación, la cola de prioridad se implementa como una lista de salto . ^{[ 30 ] [ 31 ]} Además, se utiliza una primitiva de sincronización atómica, CAS , para que la lista de salto no requiera bloqueo . Los nodos de la lista de salto constan de una clave única, una prioridad, un array de punteros , para cada nivel, a los nodos siguientes y una deletemarca. La deletemarca indica si el nodo está a punto de ser eliminado por un proceso. Esto garantiza que otros procesos puedan reaccionar a la eliminación de forma adecuada.

• insert(e)Primero, se crea un nuevo nodo con una clave y una prioridad. Además, se le asigna un número de niveles, que determina el tamaño del array de punteros. A continuación, se realiza una búsqueda para encontrar la posición correcta donde insertar el nuevo nodo. La búsqueda comienza desde el primer nodo y desde el nivel más alto. Luego, se recorre la lista de saltos hasta el nivel más bajo hasta encontrar la posición correcta. Durante la búsqueda, para cada nivel, el último nodo recorrido se guarda como nodo padre del nuevo nodo en ese nivel. Además, el nodo al que apunta el puntero del nodo padre en ese nivel se guarda como nodo sucesor del nuevo nodo en ese nivel. Posteriormente, para cada nivel del nuevo nodo, los punteros del nodo padre se establecen al nuevo nodo. Finalmente, los punteros, para cada nivel, del nuevo nodo se establecen a los nodos sucesores correspondientes.
• extract-minPrimero, se recorre la lista de nodos a omitir hasta encontrar un nodo cuya deletemarca no esté definida. Esta deletemarca se establece como verdadera para ese nodo. Finalmente, se actualizan los punteros de los nodos padres del nodo eliminado.

Si se permite el acceso concurrente a una cola de prioridad, pueden surgir conflictos entre dos procesos. Por ejemplo, se produce un conflicto si un proceso intenta insertar un nuevo nodo, pero al mismo tiempo otro proceso está a punto de eliminar el predecesor de ese nodo. ^{[ 30 ]} Existe el riesgo de que el nuevo nodo se añada a la lista de saltos, pero que ya no sea accesible. ( Ver imagen )

En este entorno, las operaciones en una cola de prioridad se generalizan a un lote de${\textstyle k}$elementos. Por ejemplo, k_extract-minelimina el${\textstyle k}$toma los elementos más pequeños de la cola de prioridad y los devuelve.

En un entorno de memoria compartida , la cola de prioridad paralela se puede implementar fácilmente utilizando árboles de búsqueda binaria paralelos y algoritmos de árbol basados ​​en uniones . En particular, k_extract-mincorresponde a una división en el árbol de búsqueda binaria que tiene${\textstyle O(\log n)}$costo y produce un árbol que contiene el${\textstyle k}$elementos más pequeños. k_insertse puede aplicar mediante una unión de la cola de prioridad original y el lote de inserciones. Si el lote ya está ordenado por la clave, k_inserttiene${\textstyle O(k\log(1+{\frac {n}{k}}))}$costo. De lo contrario, primero debemos clasificar el lote, por lo que el costo será${\textstyle O(k\log(1+{\frac {n}{k}})+k\log k)=O(k\log n)}$Otras operaciones para colas de prioridad se pueden aplicar de manera similar. Por ejemplo, k_decrease-keyse puede realizar aplicando primero differencey luego union, que primero elimina los elementos y luego los vuelve a insertar con las claves actualizadas. Todas estas operaciones son altamente paralelas, y la eficiencia teórica y práctica se puede encontrar en artículos de investigación relacionados. ^{[ 32 ] [ 33 ]}

El resto de esta sección describe un algoritmo basado en colas para memoria distribuida. Partimos de la base de que cada procesador dispone de su propia memoria local y una cola de prioridad local (secuencial). Los elementos de la cola de prioridad global (paralela) se distribuyen entre todos los procesadores.

Una k_insertoperación asigna los elementos de forma aleatoria y uniforme a los procesadores, quienes los insertan en sus colas locales. Cabe destacar que aún se pueden insertar elementos individuales en la cola. Mediante esta estrategia, los elementos globales más pequeños se encuentran, con alta probabilidad, en la unión de los elementos locales más pequeños de cada procesador. De este modo, cada procesador posee una parte representativa de la cola de prioridad global.

Esta propiedad se utiliza cuando k_extract-minse ejecuta, como el más pequeño${\textstyle m}$Los elementos de cada cola local se eliminan y se recopilan en un conjunto de resultados. Los elementos del conjunto de resultados siguen asociados a su procesador original. El número de elementos${\textstyle m}$que se elimina de cada cola local depende de${\textstyle k}$y el número de procesadores${\textstyle p}$. ^{[ 34 ]} Mediante selección paralela el${\textstyle k}$Se determinan los elementos más pequeños del conjunto de resultados. Con alta probabilidad, estos son los globales.${\textstyle k}$elementos más pequeños. Si no,${\textstyle m}$Los elementos se eliminan nuevamente de cada cola local y se colocan en el conjunto de resultados. Esto se hace hasta que la global${\textstyle k}$Los elementos más pequeños están en el conjunto de resultados. Ahora bien, estos${\textstyle k}$Se pueden devolver elementos. Todos los demás elementos del conjunto de resultados se insertan de nuevo en sus colas locales. k_extract-minSe espera el tiempo de ejecución.${\textstyle O({\frac {k}{p}}\log(n))}$, dónde${\textstyle k=\Omega (p\cdot \log(p))}$y${\textstyle n}$es el tamaño de la cola de prioridad. ^{[ 34 ]}

La cola de prioridad se puede mejorar aún más evitando que los elementos restantes del conjunto de resultados vuelvan directamente a las colas locales después de una k_extract-minoperación. Esto evita tener que mover elementos constantemente entre el conjunto de resultados y las colas locales.

Al eliminar varios elementos a la vez, se puede lograr una aceleración considerable. Pero no todos los algoritmos pueden usar este tipo de cola de prioridad. El algoritmo de Dijkstra, por ejemplo, no puede trabajar con varios nodos a la vez. El algoritmo toma el nodo con la distancia más pequeña de la cola de prioridad y calcula nuevas distancias para todos sus nodos vecinos. Si se eliminara${\textstyle k}$nodos, trabajando en un nodo podría cambiar la distancia de otro de los${\textstyle k}$nodos. Por lo tanto, el uso de operaciones de k elementos destruye la propiedad de configuración de etiquetas del algoritmo de Dijkstra.