Estoy escribiendo una biblioteca C sin bloqueo y voy a implementar una cola prioritaria. Sin embargo, el objetivo de mi biblioteca no es la integridad de las estructuras de datos, solo quiero implementar algunas típicas y luego escribir un punto de referencia mirco para mostrar que las sin bloqueo funcionan mejor en algunos casos especiales que las basadas en bloqueo . Por lo tanto, quiero saber si hay algunas aplicaciones típicas en las que la cola prioritaria desempeña un papel importante. (los proyectos de código abierto son los mejores). Entonces puedo usarlos como punto de referencia.

1
Gamer.Godot 21 ene. 2018 a las 10:41

3 respuestas

La mejor respuesta

Algunos para enumerar: 1. Algoritmo de ruta más corta de Dijkstra 2. Algoritmo de Prim 3. Códigos Huffman para la compresión de datos. 4. Heap sort 5. Equilibrio de carga en los servidores.

Hay varias aplicaciones que se señalan en:
https://www.cdn.geeksforgeeks.org/applications-priority-queue/

Además, el wiki en sí tiene una extensa lista de aplicaciones y parámetros con los que puede comparar su comparación (consulte la sección Resumen de tiempos de ejecución): https://en.wikipedia.org/wiki/Priority_queue

2
Priya Jain 21 ene. 2018 a las 08:37

Las colas de prioridad son diferentes de las colas en sienten que no actúan según el principio FIFO .

... Los elementos de la cola de prioridad se ordenan de acuerdo con su pedido natural, o por un comparador proporcionado en la construcción de la cola hora...

Uno de los ejemplos del mundo real sería el algoritmo Priority Scheduling donde se asigna una prioridad a cada trabajo y el trabajo con la prioridad más alta se programa primero

1
Ravi 21 ene. 2018 a las 08:48

Los usos más comunes para las colas prioritarias que veo en la vida real son:

1) Colas de trabajo priorizadas: cuando un subproceso está listo para más trabajo, selecciona la tarea de mayor prioridad disponible de una cola de prioridad. Esta es una gran aplicación para colas sin bloqueo.

2) Encontrar los restaurantes / hoteles / baños / lo más cercano a un lugar determinado. El algoritmo para recuperarlos de casi cualquier estructura de datos espaciales usa una cola prioritaria.

1
Matt Timmermans 22 ene. 2018 a las 13:15
48364680