Куча (приоритетная очередь)

1class MinHeap {
2  private a: number[] = []
3 
4  insert(v: number): void {
5    this.a.push(v)
6    let i = this.a.length - 1
7    while (i > 0 && this.a[i] < this.a[parent(i)]) {
8      swap(this.a, i, parent(i))
9      i = parent(i)
10    }
11  }
12 
13  extractMin(): number {
14    const min = this.a[0]
15    this.a[0] = this.a[this.a.length - 1]
16    this.a.pop()
17    this.siftDown(0)
18    return min
19  }
20 
21  private siftDown(i: number): void {
22    while (true) {
23      const l = 2 * i + 1, r = 2 * i + 2
24      let smallest = i
25      if (l < this.a.length && this.a[l] < this.a[smallest]) smallest = l
26      if (r < this.a.length && this.a[r] < this.a[smallest]) smallest = r
27      if (smallest === i) return
28      swap(this.a, i, smallest)
29      i = smallest
30    }
31  }
32}
33 
34function parent(i: number): number {
35  return Math.floor((i - 1) / 2)
36}