javascript_computer_science_exercises/binary_heaps_exercise/binaryHeapSpec.js at master · amarcjones/javascript_computer_science_exercises · 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
var expect = chai.expect
var binaryHeap

beforeEach(function(){
  binaryHeap = new MaxBinaryHeap
})

describe("#insert", function(){
  it("inserts a value at the correct position", function(){
    binaryHeap.insert(1)
    expect(binaryHeap.values[0]).to.equal(1)
    binaryHeap.insert(2)
    expect(binaryHeap.values[0]).to.equal(2)
    expect(binaryHeap.values).to.deep.equal([2, 1])
    binaryHeap.insert(3)
    expect(binaryHeap.values[0]).to.equal(3)
    expect(binaryHeap.values).to.deep.equal([3, 1, 2])
    binaryHeap.insert(4)
    expect(binaryHeap.values[0]).to.equal(4)
    expect(binaryHeap.values).to.deep.equal([4, 3, 2, 1])
    binaryHeap.insert(5)
    expect(binaryHeap.values[0]).to.equal(5)
    expect(binaryHeap.values).to.deep.equal([5, 4, 2, 1, 3])
    binaryHeap.insert(6)
    expect(binaryHeap.values[0]).to.equal(6)
    expect(binaryHeap.values).to.deep.equal([6, 4, 5, 1, 3, 2])
  });
});

describe("#remove", function(){
  it("removes a value at the correct position", function(){
    binaryHeap.insert(1)
    binaryHeap.insert(2)
    binaryHeap.insert(3)
    binaryHeap.insert(4)
    binaryHeap.insert(5)
    binaryHeap.insert(6)
    binaryHeap.remove()
    expect(binaryHeap.values[0]).to.equal(5)
    expect(binaryHeap.values).to.deep.equal([5,4,2,1,3])
    binaryHeap.remove()
    expect(binaryHeap.values).to.deep.equal([4,3,2,1])
    binaryHeap.remove()
    expect(binaryHeap.values).to.deep.equal([3,1,2])
  });
});

describe("#maxHeapify", function(){
  it("turns an array into a max binary heap", function(){
    var arr = [1,2,3,4,5,6,7,8,9,10]
    var arr2 = [5,-10,15,20,35,-2,-15,40,3,8,9]
    expect(maxHeapify(arr)).to.deep.equal([10, 9, 7, 8, 5, 6, 3, 1, 4, 2])
    expect(maxHeapify(arr2)).to.deep.equal([40, 35, 15, 20, 9, -2, -15, -10, 3, 8, 5])
  });
});