Part 4 · 1 chapters · ~8 min

Heaps and Priority Queues

The binary heap in an array, sift up and sift down, building a heap in O(n), heapsort, priority queues for schedulers and Dijkstra, top-k with bounded heaps, k-way merging, running medians, and timer wheels as an alternative for timeouts.

9

The binary heap

code
class MinHeap<T> {
  private a: T[] = [];
  constructor(private less: (x: T, y: T) => boolean) {}
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x: T) { const a = this.a; a.push(x); let i = a.length - 1;
    while (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(): T | undefined { const a = this.a; if (!a.length) return; const top = a[0], 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 && 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; }
}
// top 10 largest transfers from a stream of millions: keep a min-heap of size 10, O(n log 10)
A BINARY HEAP
a complete tree in an array, where every parent is smaller than its children
[0] 3[1] 8[2] 5[3] 12[4] 9[5] 7
swipe the figure sideways, or tap expand for full screen
1/5
array layout
A heap is stored in an array: the children of index i are 2i+1 and 2i+2, the parent is (i-1)/2. No pointers, cache-friendly.
children at 2i+1 and 2i+2a tree with no pointers