1
/**
2
 * Generic binary heap implementation with a user-provided comparator.
3
 *
4
 * Comparator contract:
5
 * - cmp(a, b) < 0  => a has higher priority than b (a comes out first)
6
 * - cmp(a, b) === 0 => a and b are equivalent in priority
7
 * - cmp(a, b) > 0  => b has higher priority than a
8
 *
9
 * Usage:
10
 *   const heap = new BinaryHeap<number>((a, b) => a - b); // min-heap
11
 *   heap.push(3); heap.push(1); heap.push(2);
12
 *   console.log(heap.pop()); // 1
13
 */
14
export type Comparator<T> = (a: T, b: T) => number;
15
 
16
export class BinaryHeap<T> {
17
  private a: T[];
18
  private cmp: Comparator<T>;
19
 
20
  constructor(cmp: Comparator<T>, items?: Iterable<T>) {
21
    this.cmp = cmp;
22
    this.a = [];
23
    if (items) {
24
      for (const it of items) this.a.push(it);
25
      if (this.a.length > 1) this.heapify();
26
    }
27
  }
28
 
29
  size(): number {
30
    return this.a.length;
31
  }
32
 
33
  isEmpty(): boolean {
34
    return this.a.length === 0;
35
  }
36
 
37
  peek(): T | undefined {
38
    return this.a[0];
39
  }
40
 
41
  push(v: T): void {
42
    this.a.push(v);
43
    this.siftUp(this.a.length - 1);
44
  }
45
 
46
  pop(): T | undefined {
47
    if (this.a.length === 0) return undefined;
48
    const top = this.a[0];
49
    const last = this.a.pop()!;
50
    if (this.a.length > 0) {
51
      this.a[0] = last;
52
      this.siftDown(0);
53
    }
54
    return top;
55
  }
56
 
57
  private heapify(): void {
58
    for (let i = Math.floor(this.a.length / 2) - 1; i >= 0; i--) this.siftDown(i);
59
  }
60
 
61
  private siftDown(i: number): void {
62
    const n = this.a.length;
63
    while (true) {
64
      const l = i * 2 + 1;
65
      const r = l + 1;
66
      let best = i;
67
      if (l < n && this.cmp(this.a[l], this.a[best]) < 0) best = l;
68
      if (r < n && this.cmp(this.a[r], this.a[best]) < 0) best = r;
69
      if (best === i) break;
70
      this.swap(i, best);
71
      i = best;
72
    }
73
  }
74
 
75
  private siftUp(i: number): void {
76
    while (i > 0) {
77
      const p = Math.floor((i - 1) / 2);
78
      if (this.cmp(this.a[i], this.a[p]) < 0) {
79
        this.swap(i, p);
80
        i = p;
81
      } else {
82
        break;
83
      }
84
    }
85
  }
86
 
87
  private swap(i: number, j: number) {
88
    const t = this.a[i];
89
    this.a[i] = this.a[j];
90
    this.a[j] = t;
91
  }
92
}