Digamos que usted está a cargo de un hospital, manejando a los pacientes en la sala de espera. Llegan todo tipo de pacientes en momentos aleatorios, cada uno con una lesión diferente. ¿Quién puede ver primero al médico y en qué orden deben ser admitidos a cirugía?
El sentido común dice que la persona más lastimada debe ser tratada primero. En otras palabras, los doctores deben ver a los pacientes en orden de cuán urgentemente necesitan tratamiento, sin importar el orden en que realmente ingresaron a la sala de espera.
Entonces, digamos que tenemos los siguientes pacientes, que llegan a la sala de espera en el siguiente orden:
- Cómo desarrollar un algoritmo
- ¿Cuál sería la mejor estrategia de negociación algorítmica simple?
- ¿Cuál es la diferencia entre trazado de rayos y fundición de rayos?
- Cómo ordenar una matriz 2D de tipo char utilizando la función C ++ sort () o qsort ()
- Tengo una pila masiva de más de 300 pares de calcetines. ¿Cuál es el algoritmo más rápido que puedo usar para extraer unos 25 pares coincidentes de la pila desordenada?
- Chico con un corte de papel (Prioridad: muy baja )
- Amigo con un hacha en la cabeza (Prioridad: MUY ALTA)
- Mujer con una mordedura de perro desagradable (Prioridad: ALTA)
- Niño que se rascó la rodilla (Prioridad: baja )
Si el hospital corre por orden de llegada, entonces el tipo con el corte de papel sería tratado antes que el tipo con el hacha en la cabeza. ¡Ese es un orden de tratamiento terrible, terrible ! El tipo con el hacha en la cabeza debe ser tratado antes que el tipo con el corte de papel, porque de lo contrario va a morir .
Para eso sirve una cola de prioridad (PQ). Si primero necesita manejar algo con una prioridad más alta, independientemente del orden en que lleguen los artículos, utilice un PQ.
Aquí hay dos aplicaciones comunes de colas prioritarias:
Heapsort
Este algoritmo es un algoritmo de ordenación, como la ordenación por inserción, mergesort, quicksort, etc. Heapsort se basa en un tipo específico de cola prioritaria llamada “montón” (por eso se llama “heapsort”).
Si se trata de números, por ejemplo, los números más pequeños obtienen una “prioridad” más alta, y los números más grandes obtienen una “prioridad” más baja. Primero arrojamos todos nuestros números al PQ en el orden que queramos. Luego, vaciamos el contenido del PQ uno a la vez. El orden de los números que salen estará en el orden de mayor prioridad a menor prioridad, como cualquier otro PQ. Dado que los números más pequeños tienen mayor prioridad, eso significa que los números saldrán del PQ en orden de menor a mayor.
¡Y ahí está tu lista ordenada de números!
Algoritmo de Dijkstra
El algoritmo de Dijkstra es un algoritmo de búsqueda de ruta de uso común que resuelve el problema de “dado un ‘laberinto’ de un montón de rutas diferentes que lo atraviesan, ¿cómo encontrar la ruta más corta desde el punto inicial del laberinto hasta el final? ?
No repasaré el algoritmo en esta respuesta (pero puedes leer sobre esto aquí). Sin embargo, una de las subrutinas en el algoritmo requiere que elija un punto intermedio en el “laberinto” que tenga la menor distancia conocida entre sí mismo y el punto de inicio. Estos puntos intermedios podrían haberse descubierto en cualquier orden arbitrario, pero lo importante es que elija el que tenga la distancia más corta entre sí mismo y el punto de partida. ¿Cuál es la forma más eficiente de hacer eso? ¡Una cola prioritaria, por supuesto! En este caso, decimos que los puntos con una distancia conocida más corta obtienen una “prioridad” más alta, y las rutas con una distancia conocida más larga obtienen una “prioridad” más baja. Para elegir el punto en el PQ que tiene la distancia más corta, todo lo que tenemos que hacer es expulsar el “siguiente elemento” en el PQ, que será, por definición, el elemento con mayor prioridad; en este caso, será el punto con la ruta más corta conocida a la ubicación inicial.
