Most urgent first
A kitchen doesn't cook in arrival order when a VIP or a delayed order needs to jump ahead. A priority queue always hands out the most urgent item. The usual implementation is a binary heap: a tree packed into an array where each parent is ≤ its children.
A min-heap in an array
class MinHeap {
#a = [];
get size() { return this.#a.length; }
peek() { return this.#a[0]; }
push(x) {
const a = this.#a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p] <= a[i]) break;
[a[p], a[i]] = [a[i], a[p]];
i = p;
}
}
pop() {
const a = this.#a;
const top = a[0];
const last = a.pop();
if (a.length) {
a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && a[l] < a[m]) m = l;
if (r < a.length && a[r] < a[m]) m = r;
if (m === i) break;
[a[m], a[i]] = [a[i], a[m]];
i = m;
}
}
return top;
}
}
const h = new MinHeap();
for (const minutes of [12, 3, 25, 7, 1, 9]) h.push(minutes);
const order = [];
while (h.size) order.push(h.pop());
console.log(order);