Card 08/ 09
Practice: Choosing the Next Patient in an Emergency Room
Patients arrive with a priority; the most urgent is always seen next.
An emergency room sees its most urgent patient next, whoever arrived first, and that is a priority queue built on a min-heap. This exercise covers keeping the waiting list as a heap through arrivals and consultations, and breaking ties so that equal priorities are seen in arrival order.
A min-heap is a complete binary tree stored in an array, in which every parent is no larger than its children, so the smallest item is at index 0. Priority 1 is the most urgent, so the next patient is at the root.
Four patients arrive, and the room sees a patient whenever a doctor is free:
- Lee arrives with priority 3.
- Mora arrives with priority 1.
- Sato arrives with priority 2.
- A doctor sees the next patient.
- Okafor arrives with priority 2.
- Doctors see the next patient three more times.
Work out the order in which the patients are seen, and the heap after each of the six events. Then decide what each heap entry must hold so that Sato, who arrived before Okafor with the same priority, is seen first. Write it in Python with heapq, or in Java with PriorityQueue.
An answer: the order, the heap after each event, and the tie-break
The order is Mora, Sato, Okafor, Lee. Each entry holds the priority, then an arrival number counting up from 0, then the name, and entries compare position by position.
Lee, (3, 0), starts the heap. Mora, (1, 1), lands at index 1 and swaps with Lee: Mora, Lee. Sato, (2, 2), lands at index 2 under Mora and stays: Mora, Lee, Sato. The first pop returns Mora and moves Sato to the root, where it stays: Sato, Lee. Okafor, (2, 3), lands under Sato; the priorities tie, and arrival 2 is smaller than 3, so Okafor stays: Sato, Lee, Okafor. The pops then return Sato, Okafor and Lee.
Without the arrival number, (2, "Okafor") and (2, "Sato") are compared by name, and a run saw Okafor first, in alphabetical rather than arrival order. The run below prints the heap after every event.
import heapq
from itertools import count
waiting = []
arrival = count()
def arrive(name, priority):
heapq.heappush(waiting, (priority, next(arrival), name))
print(f"arrive {name} (priority {priority}): {waiting}")
def see_next():
priority, order, name = heapq.heappop(waiting)
print(f"see {name} (priority {priority}): {waiting}")
return name
arrive("Lee", 3)
arrive("Mora", 1)
arrive("Sato", 2)
see_next()
arrive("Okafor", 2)
seen = [see_next() for _ in range(len(waiting))]
print("seen after Mora:", seen)
without_counter = []
for name, priority in [("Lee", 3), ("Sato", 2), ("Okafor", 2)]:
heapq.heappush(without_counter, (priority, name))
print("without the arrival number:", [heapq.heappop(without_counter)[1] for _ in range(3)])arrive Lee (priority 3): [(3, 0, 'Lee')]
arrive Mora (priority 1): [(1, 1, 'Mora'), (3, 0, 'Lee')]
arrive Sato (priority 2): [(1, 1, 'Mora'), (3, 0, 'Lee'), (2, 2, 'Sato')]
see Mora (priority 1): [(2, 2, 'Sato'), (3, 0, 'Lee')]
arrive Okafor (priority 2): [(2, 2, 'Sato'), (3, 0, 'Lee'), (2, 3, 'Okafor')]
see Sato (priority 2): [(2, 3, 'Okafor'), (3, 0, 'Lee')]
see Okafor (priority 2): [(3, 0, 'Lee')]
see Lee (priority 3): []
seen after Mora: ['Sato', 'Okafor', 'Lee']
without the arrival number: ['Okafor', 'Sato', 'Lee']In Java, a comparator on priority and then arrival does the same job, and the run saw the same order.
import java.util.Comparator;
import java.util.PriorityQueue;
public class EmergencyRoom {
record Patient(String name, int priority, long arrival) {
}
private final PriorityQueue<Patient> waiting = new PriorityQueue<>(
Comparator.comparingInt(Patient::priority).thenComparingLong(Patient::arrival));
private long arrivals = 0;
void arrive(String name, int priority) {
waiting.add(new Patient(name, priority, arrivals++));
System.out.println("arrive " + name + " (priority " + priority + "), next is " + waiting.peek().name());
}
String seeNext() {
Patient patient = waiting.poll();
System.out.println("see " + patient.name() + " (priority " + patient.priority() + "), " + waiting.size() + " waiting");
return patient.name();
}
public static void main(String[] args) {
EmergencyRoom room = new EmergencyRoom();
room.arrive("Lee", 3);
room.arrive("Mora", 1);
room.arrive("Sato", 2);
room.seeNext();
room.arrive("Okafor", 2);
room.seeNext();
room.seeNext();
room.seeNext();
}
}arrive Lee (priority 3), next is Lee
arrive Mora (priority 1), next is Mora
arrive Sato (priority 2), next is Mora
see Mora (priority 1), 2 waiting
arrive Okafor (priority 2), next is Sato
see Sato (priority 2), 2 waiting
see Okafor (priority 2), 1 waiting
see Lee (priority 3), 0 waiting← → move through sections and cards