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
// solution at https://repl.it/@swyx/Heaps-Basic-Solution
// Do not edit the class below except for the buildHeap,
// siftDown, siftUp, peek, remove, and insert methods.
class MinHeap {
  constructor(array) {
    // Do not edit the line below.
    this.heap = this.buildHeap(array);
  }

  buildHeap(array) {
    // Write your code here.
  }

  siftDown() {
    // Write your code here.
  }

  siftUp() {
    // Write your code here.
  }

  peek() {
    // Write your code here.
  }

  remove() {
    // Write your code here.
  }

  insert(value) {
    // Write your code here.
  }
}


// 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