Card 06/ 07
Practice: A Support Queue Where Urgent Tickets Jump Ahead
Tickets are handled by urgency, and in arrival order when two are equally urgent.
A help desk that serves urgent tickets first is a choice of structure made from its operations. This exercise covers listing those operations, choosing the structure, naming its built-in in Python, Java and TypeScript, and keeping equally urgent tickets in the order they arrived.
Each ticket arrives with an urgency from 1, the most urgent, to 3. Whenever an agent is free, they take the most urgent ticket waiting, and of two equally urgent tickets, the one that arrived first. Tickets arrive all day, and hundreds can be waiting at once. These five arrive in this order.
| Arrival | Summary | Urgency |
|---|---|---|
| 1 | printer jammed | 2 |
| 2 | payroll system down | 1 |
| 3 | password reset | 2 |
| 4 | new monitor request | 3 |
| 5 | site unreachable | 1 |
- List the operations and how often each runs.
- Choose the structure, and say why a sorted list and a hash map lose.
- Name the built-in in each language, and say what TypeScript needs written by hand.
- Give the order in which the five tickets are handled.
An answer: the operations, the structure and the order
Two operations run all day, and the program never needs the waiting tickets in order, only the first of them. That is a binary heap, ordered by urgency and then by arrival number.
| Operation | How often | Cost in a heap |
|---|---|---|
| Add a ticket | Every arrival | O(log n) |
| Take the most urgent, earliest ticket | Whenever an agent is free | O(log n) |
A sorted list takes the first ticket in O(1) but inserts each new one in O(n). A hash map finds a ticket by its number but knows nothing about urgency, so taking the next one means scanning all n.
A heap does not keep equal keys in arrival order, so the arrival number is part of the key: urgency first, then arrival. Python compares tuples element by element, so (urgency, arrival, summary) orders itself; Java's PriorityQueue takes a comparator; TypeScript has no heap, so its listing writes one, with comesFirst as the ordering. All three printed the same order: tickets 2, 5, 1, 3 and 4. In Python, the tuple carries the whole order.
import heapq
tickets = [("printer jammed", 2), ("payroll system down", 1), ("password reset", 2),
("new monitor request", 3), ("site unreachable", 1)]
waiting = []
for arrival, (summary, urgency) in enumerate(tickets, start=1):
heapq.heappush(waiting, (urgency, arrival, summary))
while waiting:
urgency, arrival, summary = heapq.heappop(waiting)
print(f"urgency {urgency}, ticket {arrival}: {summary}")urgency 1, ticket 2: payroll system down
urgency 1, ticket 5: site unreachable
urgency 2, ticket 1: printer jammed
urgency 2, ticket 3: password reset
urgency 3, ticket 4: new monitor requestJava states the two-part order in one comparator.
import java.util.Comparator;
import java.util.PriorityQueue;
public class SupportQueue {
record Ticket(int urgency, int arrival, String summary) {}
public static void main(String[] args) {
String[] summaries = {"printer jammed", "payroll system down", "password reset",
"new monitor request", "site unreachable"};
int[] urgencies = {2, 1, 2, 3, 1};
PriorityQueue<Ticket> waiting = new PriorityQueue<>(
Comparator.comparingInt(Ticket::urgency).thenComparingInt(Ticket::arrival));
for (int i = 0; i < summaries.length; i++) {
waiting.add(new Ticket(urgencies[i], i + 1, summaries[i]));
}
while (!waiting.isEmpty()) {
Ticket ticket = waiting.poll();
System.out.println("urgency " + ticket.urgency() + ", ticket " + ticket.arrival() + ": " + ticket.summary());
}
}
}urgency 1, ticket 2: payroll system down
urgency 1, ticket 5: site unreachable
urgency 2, ticket 1: printer jammed
urgency 2, ticket 3: password reset
urgency 3, ticket 4: new monitor requestTypeScript's heap is written out in full, as a sift up in push, which swaps a new ticket with its parent while it comes first, and a sift down in pop, which does the reverse from the root.
type Ticket = { urgency: number; arrival: number; summary: string };
function comesFirst(a: Ticket, b: Ticket): boolean {
return a.urgency !== b.urgency ? a.urgency < b.urgency : a.arrival < b.arrival;
}
class TicketHeap {
private readonly items: Ticket[] = [];
get size(): number {
return this.items.length;
}
push(ticket: Ticket): void {
const items = this.items;
items.push(ticket);
let child = items.length - 1;
while (child > 0) {
const parent = Math.floor((child - 1) / 2);
if (!comesFirst(items[child], items[parent])) break;
[items[child], items[parent]] = [items[parent], items[child]];
child = parent;
}
}
pop(): Ticket {
const items = this.items;
const top = items[0];
const last = items.pop()!;
if (items.length > 0) {
items[0] = last;
let parent = 0;
while (true) {
const left = 2 * parent + 1;
const right = left + 1;
let first = parent;
if (left < items.length && comesFirst(items[left], items[first])) first = left;
if (right < items.length && comesFirst(items[right], items[first])) first = right;
if (first === parent) break;
[items[first], items[parent]] = [items[parent], items[first]];
parent = first;
}
}
return top;
}
}
const summaries = ["printer jammed", "payroll system down", "password reset", "new monitor request", "site unreachable"];
const urgencies = [2, 1, 2, 3, 1];
const waiting = new TicketHeap();
summaries.forEach((summary, i) => waiting.push({ urgency: urgencies[i], arrival: i + 1, summary }));
while (waiting.size > 0) {
const ticket = waiting.pop();
console.log(`urgency ${ticket.urgency}, ticket ${ticket.arrival}: ${ticket.summary}`);
}urgency 1, ticket 2: payroll system down
urgency 1, ticket 5: site unreachable
urgency 2, ticket 1: printer jammed
urgency 2, ticket 3: password reset
urgency 3, ticket 4: new monitor request← → move through sections and cards