js-heap-tests/union-tests.js at master · gwtw/js-heap-tests · 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
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
'use strict';

module.exports.run = function (test, Heap) {
  test('should union the 2 heaps together given 2 heaps of size 5 with overlapping elements added in order together', function (t) {
    var heap = new Heap();
    heap.insert(0, null);
    heap.insert(2, null);
    heap.insert(4, null);
    heap.insert(6, null);
    heap.insert(8, null);
    var other = new Heap();
    other.insert(1, null);
    other.insert(3, null);
    other.insert(5, null);
    other.insert(7, null);
    other.insert(9, null);
    t.is(heap.size(), 5);
    t.is(other.size(), 5);

    heap.union(other);
    t.is(heap.size(), 10);
    for (var i = 0; i < 10; i++) {
      t.is(heap.extractMinimum().key, i);
    }
    t.true(heap.isEmpty());
  });

  test('should union the 2 heaps together given 2 heaps of size 5 with overlapping elements added in reverse order together', function (t) {
    var heap = new Heap();
    heap.insert(9, null);
    heap.insert(7, null);
    heap.insert(5, null);
    heap.insert(3, null);
    heap.insert(1, null);
    var other = new Heap();
    other.insert(8, null);
    other.insert(6, null);
    other.insert(4, null);
    other.insert(2, null);
    other.insert(0, null);
    t.is(heap.size(), 5);
    t.is(other.size(), 5);

    heap.union(other);
    t.is(heap.size(), 10);
    for (var i = 0; i < 10; i++) {
      t.is(heap.extractMinimum().key, i);
    }
    t.true(heap.isEmpty());
  });

  test('should union the 2 heaps together', function (t) {
    var heaps = constructJumbledHeaps(t);
    heaps[0].union(heaps[1]);
    t.is(heaps[0].size(), 10);
    for (var i = 0; i < 10; i++) {
      t.is(heaps[0].extractMinimum().key, i);
    }
    t.true(heaps[0].isEmpty());
  });

  test('should union the 2 heaps together after extracting the minimum from each', function (t) {
    var heaps = constructJumbledHeaps(t);
    t.is(heaps[0].extractMinimum().key, 1);
    t.is(heaps[1].extractMinimum().key, 0);
    heaps[0].union(heaps[1]);
    t.is(heaps[0].size(), 8);
    for (var i = 2; i < 10; i++) {
      t.is(heaps[0].extractMinimum().key, i);
    }
    t.true(heaps[0].isEmpty());
  });

  function constructJumbledHeaps(t) {
    var first = new Heap();
    first.insert(9, null);
    first.insert(2, null);
    first.insert(6, null);
    first.insert(1, null);
    first.insert(3, null);
    t.is(first.size(), 5);
    var second = new Heap();
    second.insert(4, null);
    second.insert(8, null);
    second.insert(5, null);
    second.insert(7, null);
    second.insert(0, null);
    t.is(second.size(), 5);
    return [first, second];
  }
};