# Who's Next in the Emergency Room? Heaps

Always call the most urgent patient next while new ones keep arriving, even on a day of 10,000: why an unsorted list and a sorted list both slow down, and the structure that fixes them, the heap, which keeps a tree in a plain array.

Journeyman · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Find a node's parent and children in a heap stored as an array
- Trace adding to and removing from a min-heap, bubbling up and down
- Choose between a list, a sorted list, one queue per level and a heap when the most urgent item must always come next, and say why

## Key takeaways

- An unsorted list makes every "who's next?" read everyone waiting, O(n); a sorted list makes every arrival slide the patients behind it along, O(n).
- A min-heap keeps every parent smaller than or equal to its children, so the smallest value, the most urgent, is always on top.
- A heap is a complete binary tree, filled level by level, so it fits in an array with no links at all: the children of index i are at 2i + 1 and 2i + 2, and its parent is at (i - 1) / 2, rounded down.
- Adding bubbles the new value up; removing the top moves the last value to the top and bubbles it down. Both are O(log n).
- With a handful of fixed priority levels, one plain queue per level is simpler and as fast; a heap earns its place when priorities have many values.

**Before this:** *A Contact List That's Fast to Search and Easy to Change: Binary Search Trees* keeps every name in order. An emergency room needs less than that: only who's at the top.

An emergency room doesn't see patients in the order they walk in. A nurse checks each new arrival and gives them an urgency level, from 1, the most urgent, to 5, the least, and whoever is most urgent is seen next, even if they arrived a minute ago. All day, two things happen over and over: a patient arrives, and a doctor asks **"who's next?"**. In a heat wave, 10,000 patients come through in one long day, faster than the doctors can see them, so the waiting list keeps growing.

Your code meets the same job whenever work comes in with priorities: a support desk's tickets, a game's next timed event, the next delivery for a driver.

## What would you try?

**An unsorted list.** An arrival goes on the end: instant. But "who's next?" has to read every waiting patient to find the most urgent, O(n). If the list grows to 10,000, the day's calls read 10,000, then 9,999, then 9,998 patients, and so on: about **50 million checks**.

**A list kept sorted by urgency.** Now "who's next?" is instant: the most urgent patient is at the front (or at the end, so nothing slides when they leave). But each arrival has to go in its place, and every patient behind that place slides along one spot: about half the list each time, O(n). Over 10,000 arrivals that's about **25 million slides**.

| What we tried | A patient arrives | "Who's next?" | 10,000 patients |
|---|---|---|---|
| Unsorted list | O(1) | O(n): read everyone | about 50 million checks |
| Sorted list | O(n): slide half the list | O(1) | about 25 million slides |

Both keep one job fast by making the other slow.

## The questions that lead to it

**What does the emergency room do most?** Arrive and "who's next?", thousands of times each. Both must be fast.

**Does the doctor ever need the whole list in order?** No. Nobody asks who's 37th. The sorted list keeps all 10,000 in order, and almost none of that order is ever used.

So what's the *least* order we can keep that still tells us the top at once? If every patient only had to be at least as urgent as a couple of patients "below" them, the most urgent would rise to the top, and a newcomer would compare with the few patients above it, not slide past half the room: **do less work by promising less.**

## How it got its name

This idea was so useful that it got a name: a **heap**, like a heap of things with the most important one on top. A heap doesn't keep everyone in order. It only promises that **the top is the most urgent**. That turns out to be enough, and it makes both arriving and "who's next?" O(log n): about 14 steps each with 10,000 waiting, under 300,000 for the whole day.

![An emergency room waiting area seen from above: patients in chairs, each with a numbered tag from 1 to 5, and a nurse at the triage desk calling the patient with tag 1, who arrived after several others. A sign on the wall reads "Most urgent first"](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/49ded7f294eb4df29f3d8f046e48ea92.webp)

Here the most urgent patient has the **smallest** number, so the heap we want keeps the smallest value on top: a **min-heap**.

## The heap's one rule

A heap is a binary tree with one rule, the **heap property**: every parent is smaller than or equal to its children. Follow any path down from the top and the numbers never get smaller. So the smallest value of all must be at the top.

That's all it promises: a parent's two children can be in either order, unlike a binary search tree's.

Flip the rule, every parent bigger than or equal to its children, and you have a **max-heap**, with the biggest value on top: the highest score, the largest order, the loudest alarm.

## A tree stored in an array

A heap is also a **complete binary tree**: it fills each level from left to right before starting the next, with no gaps. That shape means it can live in a plain array, level by level, with no links:

- the top is at index 0;
- the children of the node at index i are at **2i + 1** and **2i + 2**;
- the parent of the node at index i is at **(i - 1) / 2**, rounded down.

![A min-heap shown two ways, side by side. On the left as a tree: 1 at the top, 3 and 8 under it, and 5 and 4 under the 3. On the right as an array with five slots, indexes 0 to 4 holding 1, 3, 8, 5 and 4. Arrows from slot 1 point to its children in slots 3 and 4 (2 times 1 plus 1, and 2 times 1 plus 2), and an arrow from slot 4 points back to its parent in slot 1 ((4 minus 1) divided by 2, rounded down)](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/4386f7d3734444bfb9667db4d9019242.webp)

So the node at index 1 has its children at indexes 3 and 4, and the node at index 4 has its parent at index (4 - 1) / 2 = 1.5, rounded down to 1. No links to follow, no memory spent on them: a bit of arithmetic finds any relative.

## Adding: bubble up

To add a value, put it at the end of the array, the next free spot in the tree, so the shape stays complete. It may break the rule, so **bubble it up**: while it's smaller than its parent, swap the two. It stops when its parent is smaller or equal, or when it reaches the top.

## Removing the top: bubble down

To take the most urgent value, take the top. That leaves a hole, so move the **last** value in the array to the top, which keeps the shape complete. It's probably too big for the top, so **bubble it down**: while it's bigger than its smaller child, swap it with that child.

![Two rows of frames, each showing the heap as a tree with its array underneath. Bubbling up: 1 is added at the end of the heap 3, 5, 8 as the child of 5; it swaps with 5, then with 3, and ends at the top, giving 1, 3, 8, 5. Bubbling down: the top, 1, is removed from 1, 3, 8, 5, 4 and the last value, 4, moves to the top; 4 is bigger than its smaller child, 3, so they swap, and 4 stops above 5, giving 3, 4, 8, 5](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/c183d486a6ff495fbb187dc173bcffc4.webp)

Each swap moves one level, and a complete tree of n nodes is only about log n levels tall, so both bubble up and bubble down take O(log n) steps.

## A min-heap in code

The program adds five urgency levels, printing the array after each one, then removes the top again and again until the heap is empty.

```csharp
MinHeap waiting = new MinHeap();
foreach (int urgency in new int[] { 5, 3, 8, 1, 4 })
{
    waiting.Add(urgency);
    Console.WriteLine("Added " + urgency + ": " + waiting);
}
List<int> order = new List<int>();
while (waiting.Count > 0)
{
    order.Add(waiting.RemoveTop());
}
Console.WriteLine("Most urgent first: " + string.Join(", ", order));

class MinHeap
{
    private readonly List<int> items = new List<int>();

    public int Count => items.Count;

    public void Add(int value)
    {
        items.Add(value);
        int child = items.Count - 1;
        while (child > 0)
        {
            int parent = (child - 1) / 2;
            if (items[parent] <= items[child])
            {
                break;
            }
            (items[parent], items[child]) = (items[child], items[parent]);
            child = parent;
        }
    }

    public int RemoveTop()
    {
        int top = items[0];
        int last = items[items.Count - 1];
        items.RemoveAt(items.Count - 1);
        if (items.Count > 0)
        {
            items[0] = last;
            int parent = 0;
            while (true)
            {
                int left = 2 * parent + 1;
                int right = 2 * parent + 2;
                int smallest = parent;
                if (left < items.Count && items[left] < items[smallest])
                {
                    smallest = left;
                }
                if (right < items.Count && items[right] < items[smallest])
                {
                    smallest = right;
                }
                if (smallest == parent)
                {
                    break;
                }
                (items[parent], items[smallest]) = (items[smallest], items[parent]);
                parent = smallest;
            }
        }
        return top;
    }

    public override string ToString()
    {
        return string.Join(", ", items);
    }
}
```

```text
Added 5: 5
Added 3: 3, 5
Added 8: 3, 5, 8
Added 1: 1, 3, 8, 5
Added 4: 1, 3, 8, 5, 4
Most urgent first: 1, 3, 4, 5, 8
```

```java
class MinHeap {
    private final List<Integer> items = new ArrayList<>();

    int count() {
        return items.size();
    }

    void add(int value) {
        items.add(value);
        int child = items.size() - 1;
        while (child > 0) {
            int parent = (child - 1) / 2;
            if (items.get(parent) <= items.get(child)) {
                break;
            }
            Collections.swap(items, parent, child);
            child = parent;
        }
    }

    int removeTop() {
        int top = items.get(0);
        int last = items.remove(items.size() - 1);
        if (!items.isEmpty()) {
            items.set(0, last);
            int parent = 0;
            while (true) {
                int left = 2 * parent + 1;
                int right = 2 * parent + 2;
                int smallest = parent;
                if (left < items.size() && items.get(left) < items.get(smallest)) {
                    smallest = left;
                }
                if (right < items.size() && items.get(right) < items.get(smallest)) {
                    smallest = right;
                }
                if (smallest == parent) {
                    break;
                }
                Collections.swap(items, parent, smallest);
                parent = smallest;
            }
        }
        return top;
    }

    @Override
    public String toString() {
        return String.join(", ", items.stream().map(String::valueOf).toList());
    }
}

void main() {
    MinHeap waiting = new MinHeap();
    for (int urgency : new int[] {5, 3, 8, 1, 4}) {
        waiting.add(urgency);
        IO.println("Added " + urgency + ": " + waiting);
    }
    List<String> order = new ArrayList<>();
    while (waiting.count() > 0) {
        order.add(String.valueOf(waiting.removeTop()));
    }
    IO.println("Most urgent first: " + String.join(", ", order));
}
```

```text
Added 5: 5
Added 3: 3, 5
Added 8: 3, 5, 8
Added 1: 1, 3, 8, 5
Added 4: 1, 3, 8, 5, 4
Most urgent first: 1, 3, 4, 5, 8
```

```python
class MinHeap:
    def __init__(self):
        self.items = []

    def count(self):
        return len(self.items)

    def add(self, value):
        self.items.append(value)
        child = len(self.items) - 1
        while child > 0:
            parent = (child - 1) // 2
            if self.items[parent] <= self.items[child]:
                break
            self.items[parent], self.items[child] = self.items[child], self.items[parent]
            child = parent

    def remove_top(self):
        top = self.items[0]
        last = self.items.pop()
        if self.items:
            self.items[0] = last
            parent = 0
            while True:
                left = 2 * parent + 1
                right = 2 * parent + 2
                smallest = parent
                if left < len(self.items) and self.items[left] < self.items[smallest]:
                    smallest = left
                if right < len(self.items) and self.items[right] < self.items[smallest]:
                    smallest = right
                if smallest == parent:
                    break
                self.items[parent], self.items[smallest] = self.items[smallest], self.items[parent]
                parent = smallest
        return top

    def __str__(self):
        return ", ".join(str(value) for value in self.items)


waiting = MinHeap()
for urgency in [5, 3, 8, 1, 4]:
    waiting.add(urgency)
    print(f"Added {urgency}: {waiting}")
order = []
while waiting.count() > 0:
    order.append(str(waiting.remove_top()))
print("Most urgent first: " + ", ".join(order))
```

```text
Added 5: 5
Added 3: 3, 5
Added 8: 3, 5, 8
Added 1: 1, 3, 8, 5
Added 4: 1, 3, 8, 5, 4
Most urgent first: 1, 3, 4, 5, 8
```

```javascript
class MinHeap {
  constructor() {
    this.items = [];
  }

  count() {
    return this.items.length;
  }

  add(value) {
    this.items.push(value);
    let child = this.items.length - 1;
    while (child > 0) {
      const parent = Math.floor((child - 1) / 2);
      if (this.items[parent] <= this.items[child]) {
        break;
      }
      [this.items[parent], this.items[child]] = [this.items[child], this.items[parent]];
      child = parent;
    }
  }

  removeTop() {
    const top = this.items[0];
    const last = this.items.pop();
    if (this.items.length > 0) {
      this.items[0] = last;
      let parent = 0;
      while (true) {
        const left = 2 * parent + 1;
        const right = 2 * parent + 2;
        let smallest = parent;
        if (left < this.items.length && this.items[left] < this.items[smallest]) {
          smallest = left;
        }
        if (right < this.items.length && this.items[right] < this.items[smallest]) {
          smallest = right;
        }
        if (smallest === parent) {
          break;
        }
        [this.items[parent], this.items[smallest]] = [this.items[smallest], this.items[parent]];
        parent = smallest;
      }
    }
    return top;
  }

  toString() {
    return this.items.join(", ");
  }
}

const waiting = new MinHeap();
for (const urgency of [5, 3, 8, 1, 4]) {
  waiting.add(urgency);
  console.log(`Added ${urgency}: ${waiting}`);
}
const order = [];
while (waiting.count() > 0) {
  order.push(waiting.removeTop());
}
console.log(`Most urgent first: ${order.join(", ")}`);
```

```text
Added 5: 5
Added 3: 3, 5
Added 8: 3, 5, 8
Added 1: 1, 3, 8, 5
Added 4: 1, 3, 8, 5, 4
Most urgent first: 1, 3, 4, 5, 8
```

```typescript
class MinHeap {
  private items: number[] = [];

  count(): number {
    return this.items.length;
  }

  add(value: number): void {
    this.items.push(value);
    let child = this.items.length - 1;
    while (child > 0) {
      const parent = Math.floor((child - 1) / 2);
      if (this.items[parent] <= this.items[child]) {
        break;
      }
      [this.items[parent], this.items[child]] = [this.items[child], this.items[parent]];
      child = parent;
    }
  }

  removeTop(): number {
    const top = this.items[0];
    const last = this.items.pop()!;
    if (this.items.length > 0) {
      this.items[0] = last;
      let parent = 0;
      while (true) {
        const left = 2 * parent + 1;
        const right = 2 * parent + 2;
        let smallest = parent;
        if (left < this.items.length && this.items[left] < this.items[smallest]) {
          smallest = left;
        }
        if (right < this.items.length && this.items[right] < this.items[smallest]) {
          smallest = right;
        }
        if (smallest === parent) {
          break;
        }
        [this.items[parent], this.items[smallest]] = [this.items[smallest], this.items[parent]];
        parent = smallest;
      }
    }
    return top;
  }

  toString(): string {
    return this.items.join(", ");
  }
}

const waiting = new MinHeap();
for (const urgency of [5, 3, 8, 1, 4]) {
  waiting.add(urgency);
  console.log(`Added ${urgency}: ${waiting}`);
}
const order: number[] = [];
while (waiting.count() > 0) {
  order.push(waiting.removeTop());
}
console.log(`Most urgent first: ${order.join(", ")}`);
```

```text
Added 5: 5
Added 3: 3, 5
Added 8: 3, 5, 8
Added 1: 1, 3, 8, 5
Added 4: 1, 3, 8, 5, 4
Most urgent first: 1, 3, 4, 5, 8
```

Look at the array after the last add: 1, 3, 8, 5, 4. It isn't sorted, and it doesn't need to be. Every parent is smaller than its children, so the top is right, and each removal puts the next smallest on top. Taking everything off, one at a time, comes out sorted. The swap of two items is written `(a, b) = (b, a)` in C# and `a, b = b, a` in Python, and the same way with square brackets in JavaScript and TypeScript; Java uses `Collections.swap`. In TypeScript, the `!` after `pop()` says "this array isn't empty here", since `pop()` on an empty array gives `undefined`.

**Try it.** Add a 2 to the list of urgencies, at the end. Before you run it, work out where it goes: it starts at index 5, whose parent is index 2.

## In your textbook

Bubbling up and down are also called **sift up** and **sift down** (or *percolate*, or *heapify up* and *down*). Turning a whole array into a heap at once, called **heapify** or **build-heap**, takes only O(n). And taking everything off a heap, one at a time, sorts it in O(n log n): that's **heap sort**.

## The heap's cost card

| Operation | Big-O | Why, in everyday terms |
|---|---|---|
| See the most urgent | O(1) | It's always at the top, index 0 |
| Add | O(log n) | Bubble up at most one level per step, and there are about log n levels |
| Remove the most urgent | O(log n) | Bubble down at most one level per step |
| Find any other value | O(n) | Only the top is in a known place; anything else could be anywhere |

## When five lines win

Be honest about this emergency room: it has exactly **five** urgency levels. Give each level its own plain queue, the first-in, first-out line from Module 2. An arrival joins the back of its level's line, O(1). "Who's next?" looks at line 1, then line 2, and so on, and takes the first patient from the first line that isn't empty: at most five looks, O(1). Ties are fair for free, because each line is first come, first served. With five fixed levels, five queues beat a heap.

A heap earns its place when the priority has **many possible values**: minutes until a deadline, a distance in Module 7's route planner, the time of a game's next event, a price. Nobody wants a million queues, one per minute. So ask how many priorities there can be. A few, fixed: one queue each. Many, or any number: a heap.

## Check yourself

2 questions to try on the lesson page.

## So what

Whenever the job is "always handle the most important thing next" while new things keep arriving, a heap does it in O(log n) per step, with nothing more than an array and two bits of arithmetic. It's fast because it promises only what the job needs: the top.

## Key terms

- [Heap](https://www.ask-codey.com/glossary/heap)
- [Min-Heap](https://www.ask-codey.com/glossary/min-heap)
- [Max-Heap](https://www.ask-codey.com/glossary/max-heap)
- [Complete Binary Tree](https://www.ask-codey.com/glossary/complete-binary-tree)

## Cheat sheets

- [Who's Next in the Emergency Room? Heaps](https://www.ask-codey.com/cheat-sheets/ds-heaps-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-heaps
