A priority queue always hands out the most important item first. Build one as a generic binary heap with a comparison function.
What to build
A program that schedules tasks by priority.
Requirements
- Write
class PriorityQueue<T>with a constructor takingbefore: (a: T, b: T) => boolean, andpush(item: T),pop(): T | undefinedandsize, as a binary heap (not by sorting). add NAME Padds a task with priority P;nextremoves and printsNAME (P)for the highest priority, the earliest added among equals, oridleif there is none;sizeprintssize: S.- At the end print
left: NAME NAME ...in the order they would come out, orleft: none.
Input
Line 1: n. Then n commands.
Output
One line per next and size, then the remaining tasks.
Constraints
1 ≤ n ≤ 1000; 0 ≤ P ≤ 100.
Example
Input:
7
add email 2
add deploy 9
add lunch 2
next
size
next
next
Output:
deploy (9)
size: 2
email (2)
lunch (2)
left: none
Why it works
A heap keeps the best item at the root with O(log n) work per push and pop, the comparison function makes it generic, and the arrival number turns equal priorities into a fixed order.
Examples
Example 1 · Input
7 add email 2 add deploy 9 add lunch 2 next size next next
Expected output
deploy (9) size: 2 email (2) lunch (2) left: none
Example 2 · Input
4 next add a 0 add b 0 add c 1
Expected output
idle left: c a b
Hints
Hint 1
Store items in an array as a binary heap: the parent of index i is at floor((i - 1) / 2).
Hint 2
To break ties by arrival, store [item, order] pairs and compare the order when the priorities are equal.
Solution
Show one correct solution (try it yourself first)
const read = (): string => prompt() ?? "";
class PriorityQueue<T> {
private items: T[] = [];
constructor(private before: (a: T, b: T) => boolean) {}
get size(): number {
return this.items.length;
}
push(item: T): void {
const a = this.items;
a.push(item);
let i = a.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (!this.before(a[i], a[parent])) break;
[a[i], a[parent]] = [a[parent], a[i]];
i = parent;
}
}
pop(): T | undefined {
const a = this.items;
if (a.length === 0) return undefined;
const top = a[0];
const last = a.pop() as T;
if (a.length > 0) {
a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1;
const r = l + 1;
let best = i;
if (l < a.length && this.before(a[l], a[best])) best = l;
if (r < a.length && this.before(a[r], a[best])) best = r;
if (best === i) break;
[a[i], a[best]] = [a[best], a[i]];
i = best;
}
}
return top;
}
}
interface Task {
name: string;
priority: number;
order: number;
}
const queue = new PriorityQueue<Task>((a, b) => a.priority > b.priority || (a.priority === b.priority && a.order < b.order));
const n = Number(read());
let added = 0;
for (let i = 0; i < n; i++) {
const [command, name, p] = read().split(" ");
if (command === "add") queue.push({ name, priority: Number(p), order: added++ });
else if (command === "size") console.log("size: " + queue.size);
else {
const task = queue.pop();
console.log(task ? task.name + " (" + task.priority + ")" : "idle");
}
}
const left: string[] = [];
for (let task = queue.pop(); task; task = queue.pop()) left.push(task.name);
console.log("left: " + (left.length ? left.join(" ") : "none"));