Fair Ties, Ready-Made: Priority Queues in Your Language

See the most urgent patient first and, of two equally urgent, the one who has waited longer, with the priority queue your language already has (PriorityQueue in C# and Java, heapq in Python) or a small one in JavaScript and TypeScript, which have none.

Journeyman · Data Structures · Updated

By

After this lesson you can

  • Use your language's priority queue to take the most urgent item first
  • Order a priority queue by two things, such as urgency and then arrival time

Key takeaways

  • A heap ordered by urgency alone makes no promise about ties, and a SortedSet or TreeSet ordered by urgency alone silently drops a patient whose urgency equals another's.
  • A priority queue hands back the most important item first, whatever order the items arrived in. It's usually built on a heap.
  • To order by two things, compare the first, and only when it ties compare the second, such as urgency and then arrival.
  • C# and Java have a PriorityQueue, Python has the heapq module, and JavaScript and TypeScript have none built in.
  • All of them take the smallest first; for the biggest first, flip the comparison or make the number negative.

Before this: Who's Next in the Emergency Room? Heaps always calls the most urgent patient, but of two equally urgent patients, it can call the one who arrived later.

Five patients arrive at the emergency room, in this order:

Arrival Patient Urgency
1st Leo 3
2nd Mia 1
3rd Noah 3
4th Ola 2
5th Pia 1

Put them through the min-heap from the last lesson, ordered by urgency alone, and they're seen in the order Mia, Pia, Ola, Noah, Leo. Look at the end: Leo and Noah are both level 3, Leo has been waiting since he arrived first, and Noah went ahead of him. The heap isn't broken. It promised the most urgent on top, and it never promised anything about ties. But in a waiting room, people notice who walked in before them.

The fair order is Mia, Pia, Ola, Leo, Noah: both level 1s first (Mia arrived before Pia), then the level 2, then both level 3s (Leo before Noah).

What would you try?

Urgency only, and hope. Some nights the order comes out fair, some nights it doesn't, depending on who arrived when. A heap only promises that a parent comes before its children, so two equal patients can come out either way. In textbook words, a heap is not stable. Code that's fair most of the time is a bug that hasn't been reported yet.

A sorted set ordered by urgency. C#'s SortedSet and Java's TreeSet are the self-balancing trees from The Sorted Import That Made Search Crawl: Why Balance Matters: they keep their items in order and hand back the smallest in O(log n). But a set never holds two equal items, and when urgency is the only thing compared, Pia (urgency 1) counts as equal to Mia (urgency 1). Adding Pia changes nothing and returns false, which almost nobody checks. No error, no warning: a patient silently disappears from the list.

Re-sort the list after every arrival. A stable sort, from Module 4, keeps equal patients in the order they arrived, so the order is fair. But every arrival sorts everyone again, O(n log n) per patient: with 10,000 waiting, about 130,000 steps for one arrival.

What we tried Fair ties? Cost per arrival Where it breaks
Heap, urgency only sometimes O(log n) Noah goes before Leo
Sorted set, urgency only no: Pia vanishes O(log n) equal urgency counts as "the same patient"
Re-sort after every arrival yes O(n log n) every arrival sorts the whole room

The question that leads to it

What second fact settles a tie fairly? The order they arrived in. Give every patient an arrival number, 1, 2, 3 and so on. Compare urgency first, and only when the urgencies tie, compare arrival numbers. Now no two patients are ever equal: the heap has no ties left to get wrong, and a set would have no one to drop. And every arrival still costs O(log n).

How it got its name

A line where the most important item goes first, not the one that arrived first, is so common that it got a name: a priority queue. A priority queue is the idea, and a heap is how it's usually built. You'll use one for a support desk's most urgent tickets, a game's next timed event, and the cheapest next step in a route planner (Module 7's GPS lesson runs on one). In real code you'll rarely write the heap yourself: most languages have it ready.

The priority queue in each language

Each version gives every patient an arrival number, then adds them all to a priority queue ordered by urgency and then arrival, and takes them off one at a time.

PriorityQueue<string, (int Urgency, int Arrival)> waiting = new PriorityQueue<string, (int Urgency, int Arrival)>();
string[] names = { "Leo", "Mia", "Noah", "Ola", "Pia" };
int[] urgencies = { 3, 1, 3, 2, 1 };
for (int i = 0; i < names.Length; i++)
{
    waiting.Enqueue(names[i], (urgencies[i], i + 1));
}

int seen = 1;
while (waiting.TryDequeue(out string? name, out (int Urgency, int Arrival) priority))
{
    Console.WriteLine(seen + ". " + name + " (urgency " + priority.Urgency + ")");
    seen++;
}
1. Mia (urgency 1)
2. Pia (urgency 1)
3. Ola (urgency 2)
4. Leo (urgency 3)
5. Noah (urgency 3)
record Patient(String name, int urgency, int arrival) {}

void main() {
    PriorityQueue<Patient> waiting = new PriorityQueue<>(
        Comparator.comparingInt(Patient::urgency).thenComparingInt(Patient::arrival));
    String[] names = {"Leo", "Mia", "Noah", "Ola", "Pia"};
    int[] urgencies = {3, 1, 3, 2, 1};
    for (int i = 0; i < names.length; i++) {
        waiting.add(new Patient(names[i], urgencies[i], i + 1));
    }

    int seen = 1;
    while (!waiting.isEmpty()) {
        Patient patient = waiting.poll();
        IO.println(seen + ". " + patient.name() + " (urgency " + patient.urgency() + ")");
        seen++;
    }
}
1. Mia (urgency 1)
2. Pia (urgency 1)
3. Ola (urgency 2)
4. Leo (urgency 3)
5. Noah (urgency 3)
import heapq

waiting = []
names = ["Leo", "Mia", "Noah", "Ola", "Pia"]
urgencies = [3, 1, 3, 2, 1]
for i in range(len(names)):
    heapq.heappush(waiting, (urgencies[i], i + 1, names[i]))

seen = 1
while waiting:
    urgency, arrival, name = heapq.heappop(waiting)
    print(f"{seen}. {name} (urgency {urgency})")
    seen += 1
1. Mia (urgency 1)
2. Pia (urgency 1)
3. Ola (urgency 2)
4. Leo (urgency 3)
5. Noah (urgency 3)
class PriorityQueue {
  constructor(comesFirst) {
    this.comesFirst = comesFirst;
    this.items = [];
  }

  get size() {
    return this.items.length;
  }

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

  take() {
    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 first = parent;
        if (left < this.items.length && this.comesFirst(this.items[left], this.items[first])) {
          first = left;
        }
        if (right < this.items.length && this.comesFirst(this.items[right], this.items[first])) {
          first = right;
        }
        if (first === parent) {
          break;
        }
        [this.items[parent], this.items[first]] = [this.items[first], this.items[parent]];
        parent = first;
      }
    }
    return top;
  }
}

const waiting = new PriorityQueue((a, b) =>
  a.urgency !== b.urgency ? a.urgency < b.urgency : a.arrival < b.arrival);
const names = ["Leo", "Mia", "Noah", "Ola", "Pia"];
const urgencies = [3, 1, 3, 2, 1];
for (let i = 0; i < names.length; i++) {
  waiting.add({ name: names[i], urgency: urgencies[i], arrival: i + 1 });
}

let seen = 1;
while (waiting.size > 0) {
  const patient = waiting.take();
  console.log(`${seen}. ${patient.name} (urgency ${patient.urgency})`);
  seen++;
}
1. Mia (urgency 1)
2. Pia (urgency 1)
3. Ola (urgency 2)
4. Leo (urgency 3)
5. Noah (urgency 3)
class PriorityQueue<T> {
  private items: T[] = [];
  private comesFirst: (a: T, b: T) => boolean;

  constructor(comesFirst: (a: T, b: T) => boolean) {
    this.comesFirst = comesFirst;
  }

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

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

  take(): T {
    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 first = parent;
        if (left < this.items.length && this.comesFirst(this.items[left], this.items[first])) {
          first = left;
        }
        if (right < this.items.length && this.comesFirst(this.items[right], this.items[first])) {
          first = right;
        }
        if (first === parent) {
          break;
        }
        [this.items[parent], this.items[first]] = [this.items[first], this.items[parent]];
        parent = first;
      }
    }
    return top;
  }
}

interface Patient {
  name: string;
  urgency: number;
  arrival: number;
}

const waiting = new PriorityQueue<Patient>((a, b) =>
  a.urgency !== b.urgency ? a.urgency < b.urgency : a.arrival < b.arrival);
const names = ["Leo", "Mia", "Noah", "Ola", "Pia"];
const urgencies = [3, 1, 3, 2, 1];
for (let i = 0; i < names.length; i++) {
  waiting.add({ name: names[i], urgency: urgencies[i], arrival: i + 1 });
}

let seen = 1;
while (waiting.size > 0) {
  const patient = waiting.take();
  console.log(`${seen}. ${patient.name} (urgency ${patient.urgency})`);
  seen++;
}
1. Mia (urgency 1)
2. Pia (urgency 1)
3. Ola (urgency 2)
4. Leo (urgency 3)
5. Noah (urgency 3)

The five languages give you three different starting points:

  • C#'s PriorityQueue<TElement, TPriority> keeps each item apart from its priority. Here the priority is a pair, (Urgency, Arrival), and C# compares pairs one part at a time: urgency first, arrival only on a tie.
  • Java's PriorityQueue<E> takes a Comparator, built here with comparingInt and then thenComparingInt, which reads like the rule itself: by urgency, then by arrival.
  • Python's everyday choice is the heapq module, which turns a plain list into a min-heap. (Its queue.PriorityQueue class is meant for programs that run several threads at once, and uses heapq inside.) Python compares tuples part by part, so (urgency, arrival, name) sorts by urgency, then arrival.
  • JavaScript and TypeScript have no priority queue at all, so their version is the min-heap from the last lesson, with one change: instead of <, it asks a comesFirst function which of two items goes first, so the same class works for patients, tickets or anything else.

Smallest first, or biggest first?

All four of these take the smallest first: they're min-heaps. When you need the biggest first, such as the highest score:

  • C#: give the priority a comparer that flips the order, Comparer<int>.Create((a, b) => b.CompareTo(a));
  • Java: new PriorityQueue<>(Comparator.reverseOrder());
  • Python: push the negative of the number, -score, and flip it back when you pop it;
  • JavaScript and TypeScript: pass a comesFirst that says a > b.

Try it. A new patient, Quinn, arrives sixth with urgency 2. Add Quinn to the names and urgencies, and before you run it, say where Quinn will be seen: after Ola, who also has urgency 2 but arrived earlier.

The priority queue's cost card

Operation Big-O Why, in everyday terms
Add an item O(log n) It bubbles up through about log n levels
Take the most important O(log n) The last item bubbles down from the top
See the most important without taking it O(1) It's at the top (Peek in C#, peek in Java, waiting[0] in Python)
Find or remove any other item O(n) Only the top is in a known place

The rival from the last lesson still stands: with a few fixed urgency levels, one plain queue per level is fair and O(1). The priority queue is the one to reach for when priorities have many values, or when the rule is more than one number, such as urgency and then arrival.

Check yourself

2 questions to try on the lesson page.

So what

When "what's next" depends on importance and not on arrival, reach for a priority queue, give it a clear rule for what comes first, and break ties with a second rule so the order is fair. In JavaScript and TypeScript, the heap you wrote is the priority queue.

Key terms

Cheat sheets