TypeScript: A generic priority queue

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 taking before: (a: T, b: T) => boolean, and push(item: T), pop(): T | undefined and size, as a binary heap (not by sorting).
  • add NAME P adds a task with priority P; next removes and prints NAME (P) for the highest priority, the earliest added among equals, or idle if there is none; size prints size: S.
  • At the end print left: NAME NAME ... in the order they would come out, or left: 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"));

Lesson: Generic classes and typed collections →