Heaps

Keep the smallest (or largest) item one step away while items keep arriving, without sorting everything again.

Start with the first problem

Draft. This pattern and its problems have not been reviewed by a second person yet.

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;
  }
}

Problems

In order of difficulty
  1. Not started
  2. Not started
Esc
↑ ↓ to move↵ to open