algorithm - estructura - ¿Cuándo usaría una cola de prioridad?
colas estructura de datos (5)
Aquí está la lista: Simulación dirigida por eventos: clientes en una línea, partículas en colisión
Cálculo numérico. Reduciendo el error de redondeo . Compresión de datos. Códigos de Huffman que comprimen los datos. Búsqueda de gráficos : algoritmo de Dijkstra, algoritmo de Prim Teoría de números: suma de potencias Inteligencia artificial: A * estadísticas de búsqueda : mantener los valores M más grandes en una secuencia Sistemas operativos: equilibrio de carga, manejo de interrupciones Optimización discreta. embalaje de la bandeja, programación de filtrado de spam. Filtro de spam bayesiano
El único ejemplo de uso de la cola de prioridad que conozco es el algoritmo de Dijkstra (para calcular el costo mínimo)
¿En qué otras situaciones sería útil?
Aquí hay un ejemplo práctico: para una aplicación empresarial:
Usted está administrando un hospital y los pacientes están ingresando. Sólo hay un médico en el personal. El primer hombre entra, y es servido inmediatamente. A continuación, un hombre con un resfriado entra y necesita ayuda. Lo agrega a la cola y él espera en la fila para que el médico esté disponible. A continuación, un hombre con un hacha en la cabeza entra por la puerta. Se le asigna una prioridad más alta porque tiene una mayor responsabilidad médica. Así que el hombre con el frío es golpeado en línea. A continuación, alguien entra con problemas respiratorios. Así que, una vez más, el hombre con el frío es golpeado en prioridad. Esto se denomina triaging en el mundo real, pero en este caso es una línea médica.
Implementar esto en el código usaría una cola de prioridad y un hilo de trabajo (el médico) para realizar el trabajo en los consumibles / unidades de trabajo (los pacientes)
Escanee a través de una gran colección de estadísticas para informar los principales N artículos: N conexiones de red más concurridas, N clientes más valiosos, N usuarios de discos más grandes ...
Hay muchas aplicaciones de la cola de prioridad (min / max heap). Pero si está buscando algoritmos clásicos y famosos, el algoritmo de Prim para un ejemplo usa la cola de prioridad.
Una cola de prioridad basada en un montón está ordenando parcialmente la secuencia de entrada. Esto tiene ventajas sobre la clasificación inmediata cuando no necesita toda la secuencia, ya que mcdowella dio algunos ejemplos para. En particular, si solo necesita m de los n elementos, tiene O (m log n) complejidad. Una segunda ventaja es cuando está agregando elementos dinámicamente, es decir, cuando no conoce toda la secuencia de antemano. Con el montón como almacenamiento de respaldo, agregar otro elemento es más rápido que insertarlo en una secuencia ordenada.
Además, cuando está haciendo estallar elementos individuales en un orden ordenado y luego los descarta (es decir, no necesita la secuencia ordenada posteriormente), usar una cola de prioridad le da al lector el mensaje correcto. También facilita el intercambio de diferentes implementaciones, por ejemplo, una basada en un montón o una que ordena la secuencia de entrada de antemano. Sin embargo, esta es una cuestión de gusto, siempre puedes lograr lo mismo usando cualquier secuencia que uses en consecuencia, pero esto solo hace que el código sea más difícil de leer.