Minimum Difference in Sums After Removal of Elements LeetCode solution in JavaScript

1
/**
2
 * @param {number[]} nums
3
 * @return {number}
4
 */
5
var minimumDifference = function (nums) {
6
  //Creating heap
7
  class Heap {
8
    constructor(type) {
9
      this.type = type;
10
      this.data = [];
11
      this.data[0] = undefined;
12
    }
13
    print() {
14
      for (let i = 1; i < this.data.length; i++) {
15
        console.log(this.data[i]);
16
      }
17
    }
18
    getSize() {
19
      return this.data.length - 1;
20
    }
21
    insert(value) {
22
      this.data.push(value);
23
      if (this.data.length == 2) {
24
        return;
25
      }
26
      let lastIndex = this.data.length - 1;
27
      while (
28
        this.data[Math.floor(lastIndex / 2)] !== undefined &&
29
        this.compare(
30
          this.data[lastIndex],
31
          this.data[Math.floor(lastIndex / 2)]
32
        ) > 0
33
      ) {
34
        let temp = this.data[Math.floor(lastIndex / 2)];
35
        this.data[Math.floor(lastIndex / 2)] = this.data[lastIndex];
36
        this.data[lastIndex] = temp;
37
        lastIndex = Math.floor(lastIndex / 2);
38
      }
39
    }
40
    //This returns a positive number if a is greater than b. Here meaing of being greater depends on the type of heap. For max heap it will return positive number if a>b and for min heap it will return positive number if a<b .
41
    compare(a, b) {
42
      if (this.type === "min") {
43
        return b - a;
44
      } else {
45
        return a - b;
46
      }
47
    }
48
    removeTop() {
49
      let max = this.data[1];
50
      if (this.getSize() > 1) {
51
        this.data[1] = this.data.pop();
52
        this.heapify(1);
53
      } else {
54
        //If the size is 0 then just remove the element, no shifting and hipify will be applicable
55
        this.data.pop();
56
      }
57
      return max;
58
    }
59
    getTop() {
60
      let max = null;
61
      if (this.getSize() >= 1) {
62
        max = this.data[1];
63
      }
64
      return max;
65
    }
66
    heapify(pos) {
67
      if (pos * 2 > this.data.length - 1) {
68
        //That means element at index 'pos' is not having any child
69
        return;
70
      }
71
      if (
72
        (this.data[pos * 2] !== undefined &&
73
          this.compare(this.data[pos * 2], this.data[pos]) > 0) ||
74
        (this.data[pos * 2 + 1] !== undefined &&
75
          this.compare(this.data[pos * 2 + 1], this.data[pos]) > 0)
76
      ) {
77
        if (
78
          this.data[pos * 2 + 1] === undefined ||
79
          this.compare(this.data[pos * 2 + 1], this.data[pos * 2]) <= 0
80
        ) {
81
          let temp = this.data[pos * 2];
82
          this.data[pos * 2] = this.data[pos];
83
          this.data[pos] = temp;
84
          this.heapify(pos * 2);
85
        } else {
86
          let temp = this.data[pos * 2 + 1];
87
          this.data[pos * 2 + 1] = this.data[pos];
88
          this.data[pos] = temp;
89
          this.heapify(pos * 2 + 1);
90
        }
91
      }
92
    }
93
  }
94
  let maxHeap = new Heap(),
95
    minHeap = new Heap("min"),
96
    sum = 0;
97
  let n = nums.length / 3,
98
    leftArr = [],
99
    rightArr = [];
100
  for (let i = 0; i < 2 * n; i++) {
101
    if (maxHeap.getSize() < n) {
102
      sum += nums[i];
103
      maxHeap.insert(nums[i]);
104
    } else {
105
      if (maxHeap.getTop() > nums[i]) {
106
        let top = maxHeap.removeTop();
107
        sum -= top;
108
        sum += nums[i];
109
        maxHeap.insert(nums[i]);
110
      }
111
    }
112
    if (maxHeap.getSize() === n) {
113
      leftArr.push(sum);
114
    }
115
  }
116
  sum = 0;
117
  for (let i = 3 * n - 1; i >= n; i--) {
118
    if (minHeap.getSize() < n) {
119
      sum += nums[i];
120
      minHeap.insert(nums[i]);
121
    } else {
122
      if (minHeap.getTop() < nums[i]) {
123
        let top = minHeap.removeTop();
124
        sum -= top;
125
        sum += nums[i];
126
        minHeap.insert(nums[i]);
127
      }
128
    }
129
    if (minHeap.getSize() === n) {
130
      rightArr.push(sum);
131
    }
132
  }
133
  rightArr.reverse();
134
  let min = Number.MAX_SAFE_INTEGER;
135

136
  for (let i = 0; i < leftArr.length; i++) {
137
    min = Math.min(min, leftArr[i] - rightArr[i]);
138
  }
139
  return min;
140
};