main.js
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// solution for https://repl.it/@swyx/Heaps-Basic-Bare
// Do not edit the class below except for the buildHeap,
// siftDown, siftUp, peek, remove, and insert methods.
class MinHeap {
  constructor(array) {
    this.heap = this.buildHeap(array);
  }

  // O(n) time | O(1) space
  buildHeap(array) {
    const firstParentIdx = Math.floor((array.length - 2) / 2);
    for (let currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
      this.siftDown(currentIdx, array.length - 1, array);
    }
    return array;
  }

  // O(log(n)) time | O(1) space
  siftDown(currentIdx, endIdx, heap) {
    let childOneIdx = currentIdx * 2 + 1;
    while (childOneIdx <= endIdx) {
      const childTwoIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
      let idxToSwap;
      if (childTwoIdx !== -1 && heap[childTwoIdx] < heap[childOneIdx]) {
        idxToSwap = childTwoIdx;
      } else {
        idxToSwap = childOneIdx
      }
      if (heap[idxToSwap] < heap[currentIdx]) {
        this.swap(currentIdx, idxToSwap, heap);
        currentIdx = idxToSwap;
        childOneIdx = currentIdx * 2 + 1;
      } else {
        return;
      }
    }
  }

  // O(log(n)) time | O(1) space
  siftUp(currentIdx, heap) {
    let parentIdx = Math.floor((currentIdx - 1) / 2);
    while (currentIdx > 0 && heap[currentIdx] < heap[parentIdx]) {
      this.swap(currentIdx, parentIdx, heap);
      currentIdx = parentIdx;
      parentIdx = Math.floor((currentIdx - 1) / 2)
    }
  }

  // O(1) time | O(1) space
  peek() {
    return this.heap[0];
  }

  // O(log(n)) time | O(1) space
  remove() {
    this.swap(0, this.heap.length - 1, this.heap);
    const valueToRemove = this.heap.pop();
    this.siftDown(0, this.heap.length - 1, this.heap);
    return valueToRemove;
  }

  // O(log(n)) time | O(1) space
  insert(value) {
    this.heap.push(value);
    this.siftUp(this.heap.length - 1, this.heap);
  }

  swap(i, j, heap) {
    const temp = heap[j];
    heap[j] = heap[i];
    heap[i] = temp;
  }
}


// Tests - basically only checks to ensure that you build heaps which are valid 
// i.e. children >= parents (this is a minHeap)
const chai = require("chai");
const test1 = new MinHeap([2, 3, 1])
chai.expect(test1.heap[0] === Math.min.apply(null, test1.heap)).to.deep.equal(true) && console.log('Test1 passed')
for (let currentIdx = test1.heap.length - 1; currentIdx >= 0; currentIdx--) {
  let parentIdx = Math.floor((currentIdx - 1) / 2);
  if (parentIdx < 0) break;
  chai.expect(test1.heap[currentIdx] >= test1.heap[parentIdx]).to.deep.equal(true) && console.log('Test1 passed ' + currentIdx)
}

const test2 = new MinHeap([48, 12, 24, 7, 8, -5, 24, 391, 24, 56, 2, 6, 8, 41])
test2.insert(76);
test2.remove();
test2.remove();
test2.insert(87);

chai.expect(test2.heap[0] === Math.min.apply(null, test2.heap)).to.deep.equal(true) && console.log('Test2 passed')
for (let currentIdx = test2.heap.length - 1; currentIdx >= 0; currentIdx--) {
  let parentIdx = Math.floor((currentIdx - 1) / 2);
  if (parentIdx < 0) break;
  chai.expect(test2.heap[currentIdx] >= test2.heap[parentIdx]).to.deep.equal(true) && console.log('Test2 passed' + currentIdx)
}
Native Browser JavaScript