CodingTest/test.js at master · dooking/CodingTest · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class MinHeap {
  constructor() {
    this.heap = [null];
  }
  push(element) {
    this.heap.push(element);
    let curIdx = this.heap.length - 1;
    while (curIdx > 1) {
      if (this.heap[curIdx] < this.heap[Math.floor(curIdx / 2)]) {
        [this.heap[curIdx], this.heap[Math.floor(curIdx / 2)]] = [
          this.heap[Math.floor(curIdx / 2)],
          this.heap[curIdx],
        ];
        curIdx = Math.floor(curIdx / 2);
      } else {
        break;
      }
    }
    return;
  }
  pop() {
    let removeItem = this.heap[1];
    this.heap[1] = this.heap[this.heap.length - 1];
    this.heap.pop();
    let curIdx = 1;
    while (curIdx < this.heap.length) {
      let minIdx = curIdx;
      let leftIdx = curIdx * 2;
      let rightIdx = curIdx * 2 + 1;

      if (
        leftIdx < this.heap.length &&
        this.heap[leftIdx] < this.heap[minIdx]
      ) {
        minIdx = leftIdx;
      }
      if (
        rightIdx < this.heap.length &&
        this.heap[rightIdx] < this.heap[minIdx]
      ) {
        minIdx = rightIdx;
      }
      if (minIdx !== curIdx) {
        [this.heap[curIdx], this.heap[minIdx]] = [
          this.heap[minIdx],
          this.heap[curIdx],
        ];
        curIdx = minIdx;
      } else {
        break;
      }
    }
    return removeItem;
  }
}