Exercise: Emergency Room Triage

Build an emergency room's waiting list: most urgent first, fair ties, arrivals and calls all night, and a 100,000-patient disaster drill in under 3 seconds; then see what the same structure does for Module 7's maps and routes.

Journeyman · Data Structures · Updated

By

Here's the ticket from the charge nurse at City General's emergency room:

Our waiting-list app calls patients by urgency, from 1, the most urgent, to 5, the least.

  1. Most urgent first. "Who's next?" always gives the most urgent patient waiting, even one who walked in a minute ago.
  2. Fair ties. Two patients with the same urgency are seen in the order they arrived.
  3. Arrivals all night, "who's next?" all night. Neither may slow down as the room fills up.
  4. The board shows who's next without calling them, and how many are waiting.

Too slow: every year the region's disaster drill sends 100,000 pretend patients through the app, all waiting at once, then called one by one. The whole drill has to finish in under 3 seconds.

This is the emergency room from Who's Next in the Emergency Room? Heaps, with the fair ties from Fair Ties, Ready-Made: Priority Queues in Your Language. You write it yourself, so you know exactly what a priority queue does when you call one.

Before you start

You need one language set up, as in Setup: VS Code and Your Language. The exercise is written in all five of the course's languages; pick the one you use.

Get the exercise code

Open this lesson's GitHub repository, github.com/ask-codey/exercise-ds-er-triage, also linked from the Exercise box beside the lesson. Clone it into your course folder. In a terminal, in that folder:

git clone https://github.com/ask-codey/exercise-ds-er-triage.git

Git makes a folder, exercise-ds-er-triage, with the exercise code inside.

The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:

  • your code: the TriageQueue class, with its methods to finish (the repository's README.md names the file for each language);
  • the Patient class: a name, an urgency and an arrival number. You don't need to change it;
  • the tests that check your methods. You don't need to change them either;
  • a demo program that tries your waiting list on five patients.

In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.

What to do

The class already has its heap, an empty list, and an arrivals counter that starts at 0. Every method you finish is there, with its parameters, and does nothing or returns an empty answer for now. The comment above each one says what it should do, with examples, and ends with a Growth rate: line. Here is next in Python, as the starter has it (the other languages say the same in their own syntax):

def next(self):
    """
    Take the next patient to be seen off the list and return their name:
    the most urgent, and of those, the one who arrived first. Move the
    last patient to the top and bubble them down. Return None when
    nobody is waiting.

    After the five patients in demo.py: next() -> "Mia", then "Pia".

    Growth rate: (write it here)
    """
    return None
  1. Decide who comes first. Write a small helper: patient a comes before patient b when a is more urgent (a smaller number), or when they're equally urgent and a arrived earlier.
  2. A patient arrives. Finish add: add one to the arrival counter, put a new Patient at the end of the heap, and bubble them up.
  3. Call the next patient. Finish next: keep the top patient, move the last one to the top, bubble them down, and return the top patient's name (or nothing when nobody is waiting).
  4. See who's next. Finish peek and heapOrder.
  5. Name the growth rates. On each method's Growth rate: line, write its Big-O and a few words on why.

Use your own heap, not your language's built-in priority queue: one test checks the heap's own order, step by step, the way the lesson's pictures bubble.

Check your work

Each language has its own command, run in the terminal in your language's folder (Terminal > New Terminal in VS Code). The repository's README.md has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (npm install).

Language Run the tests Run the demo
C# dotnet test dotnet run --project ErTriage
Java ./mvnw test (.\mvnw test in PowerShell) java src/main/java/Demo.java
Python python -m pytest python demo.py
JavaScript npm test node demo.js
TypeScript npm test node demo.ts

At first all 9 tests fail. That's expected: each method you finish turns its tests green. A failing test's message starts with Not yet: and says what it expected, for example Not yet: urgency 1 first (Mia arrived before Pia), then urgency 2, then urgency 3 (Leo arrived before Noah). The last two run a busy night of 10,000 patients, then the 100,000-patient drill against the clock.

<details> <summary>Stuck?</summary>

  • Where to look: the ticket asks for what Who's Next in the Emergency Room? Heaps builds, a min-heap, ordered by urgency and then arrival, as in Fair Ties, Ready-Made: Priority Queues in Your Language.
  • Bubble up is a loop: while the patient isn't at the top and comes before their parent, at index (i - 1) / 2 rounded down, swap the two and move up.
  • Bubble down is a loop too: look at both children, at 2i + 1 and 2i + 2 (when they exist), pick the one that comes first, and swap with it only if it comes before the patient you're moving. Stop when neither child does.
  • Ties are what the arrival number is for. If Ana, Ben and Cal all have urgency 2 and come out in the wrong order, check that your helper compares arrivals when the urgencies are equal.
  • Don't forget the last patient. When next takes the only patient, there's nobody left to move to the top.
  • Stuck on a growth rate? The heap is a complete binary tree, about log n levels tall, and each swap moves one level. The cost card in Who's Next in the Emergency Room? Heaps has the rest.

</details>

When you're done

Every test is green, and the demo prints the same lines in every language:

Waiting, in heap order: Mia, Pia, Noah, Leo, Ola
Next: Mia
Next: Pia
Next: Ola
Next: Leo
Next: Noah
Next: nobody waiting

Look at the first line. The heap's own order, Mia, Pia, Noah, Leo, Ola, isn't the order patients are seen in, and it never needs to be. Why is Noah ahead of Ola in the list, even though Ola is seen first?

<details> <summary>Why Should I Choose This?</summary>

The drill is 100,000 patients waiting at once, then called one by one.

  • An unsorted list, read on every call: each "who's next?" reads everyone still waiting, O(n): about 5 billion comparisons, 38 seconds in C# and about five minutes in Python.
  • A list kept sorted: each call is instant, but each arrival slides the patients behind its place along, O(n). Computers slide memory in big blocks, so 100,000 can still pass, but ten times the patients is a hundred times the sliding.
  • One plain queue per urgency level: honestly, with exactly five levels this passes the drill too, in O(1) per arrival and per call, with fair ties for free. It stops working when the priority has many values, such as minutes until a deadline or the distance to the next stop on a route.
  • Your heap: an arrival and a call each move one patient at most one level per step, and 100,000 patients make only 17 levels: O(log n), for any kind of priority. It passes the drill in about a second in Python, and a fraction of one in the other languages.

</details>

Where else does this shape show up?

This chapter built two shapes: "always the most important next", and "everything that starts with this". Before you open the answers, think of three other places, on a screen or in daily life, where each one shows up.

<details> <summary>Some answers</summary>

  • A game keeps its timed events (a door opens in 3 seconds, a power-up ends in 10) so the soonest is always next: a heap.
  • A support desk hands the most urgent ticket to the next free agent: a priority queue.
  • A music app's "top 10 most played" picks the best few out of millions with a small heap.
  • A route planner always explores the closest place it hasn't settled yet: a priority queue, in Module 7.
  • A search box suggests cities as you type, and a phone's contacts narrow down with each letter: a trie.
  • A spell checker walks a trie to find words that start the way your misspelling does.

</details>

Submit your exercise

The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.

  1. On GitHub, click +, then New repository. Name it (for example exercise-ds-er-triage), choose Public, and click Create repository. Leave out the README: your folder already has one.

  2. In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:

    git remote set-url origin https://github.com/your-name/exercise-ds-er-triage.git
    git add .
    git commit -m "My solution"
    git push -u origin main
    
  3. Paste your repo's address, such as https://github.com/your-name/exercise-ds-er-triage, into Submit your exercise on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.

Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.

What Module 7 unlocks

Every structure in this module had one starting point and branches that never met again: a tree. Module 7, Graphs, and Choosing Well, lets the branches meet. A subway map, a road network or a group of friends is a graph: places joined to places, in any pattern, loops and all. You'll walk graphs with the same two ideas you used on trees, a queue for level by level and a stack (or recursion) for as deep as you can go, and find the fewest stops between two stations. Then the heap you just built comes back: with a priority queue that always picks the closest place not yet settled, Dijkstra's algorithm finds the fastest route on a map, the way a GPS does. Your waiting room's "who's next?" becomes "which station next?". The module ends with how to choose the right structure for any job, and say why out loud.

So what

You've built the structure behind every "most urgent first" list: a few swaps per patient, whether ten are waiting or ten thousand. When you call a priority queue from now on, you know what's happening inside it, and why each call is O(log n).

Key terms

Related