Some problems need the smallest item over and over while the set keeps changing: the shortest job waiting, the k largest values so far, the next timer to fire. Sorting after every change is wasteful; scanning for the minimum each time is quadratic.
A binary heap keeps items in an array arranged as a tree: each item is no larger than its two children, at positions 2i + 1 and 2i + 2. The smallest is always at position 0. Adding an item puts it at the end and swaps it up past larger parents; removing the smallest moves the last item to the top and swaps it down past smaller children. Both take O(log n) steps.
JavaScript has no built-in heap, so you write one, about twenty lines. Give it a comparison function, so the same heap can order jobs by duration, then arrival, then position.
A useful trick: to keep the k largest items, use a min-heap of size k. Its top is the smallest of the k largest, which is exactly the k-th largest, and a new item only enters if it beats that top.
Recognise it
- You repeatedly need the smallest or largest of a changing set.
- Only the top k items matter, out of many.
- Events or jobs must be processed in order of a priority, not of arrival.
The shape of the code
class Heap {
constructor(less) { this.a = []; this.less = less; }
get size() { return this.a.length; }
peek() { return this.a[0]; }
push(x) {
const a = this.a; a.push(x);
for (let i = a.length - 1; i > 0;) {
const p = (i - 1) >> 1;
if (!this.less(a[i], a[p])) break;
[a[i], a[p]] = [a[p], a[i]]; i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(a[l], a[m])) m = l;
if (r < a.length && this.less(a[r], a[m])) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]]; i = m;
}
}
return top;
}
}