1
/**
2
 * @param {number[]} piles
3
 * @param {number} k
4
 * @return {number}
5
 */
6
var minStoneSum = function (piles, k) {
7
  const heap = new Heap(piles);
8

9
  let i = 0;
10
  while (i < k) {
11
    //TAKE THE TOP MAX VALUE TO REDUCE
12
    let top = heap.dequeue();
13
    let updated = top - ~~(top / 2);
14

15
    //IF AFTER  UPDATION VALUE IS NOT 0 THEN INSERT AGAIN
16
    if (updated) {
17
      heap.enqueue(updated);
18
    }
19
    i++;
20
  }
21
  return heap.getTree().reduce((acc, v) => acc + v, 0);
22
};
23

24
class Heap {
25
  constructor(list = []) {
26
    this.tree = [null];
27
    this.list = list;
28
    this.build();
29
  }
30

31
  build() {
32
    for (let priority of this.list) this.enqueue(priority);
33
  }
34

35
  swap(pos1, pos2) {
36
    [this.tree[pos1], this.tree[pos2]] = [this.tree[pos2], this.tree[pos1]];
37
  }
38

39
  enqueue(priority) {
40
    this.tree[this.tree.length] = priority;
41
    let i = this.tree.length - 1,
42
      parent = ~~(i / 2);
43
    while (i > 1) {
44
      if (this.tree[parent] < this.tree[i]) this.swap(parent, i);
45
      i = parent;
46
      parent = ~~(i / 2);
47
    }
48
  }
49

50
  dequeue() {
51
    let size = this.tree.length - 1,
52
      pos = 1;
53
    if (!size) return;
54

55
    let last = this.tree.pop(),
56
      deleted = this.tree[pos];
57

58
    if (!deleted && last) return last;
59

60
    this.tree[pos] = last;
61
    this.heapify(pos);
62
    return deleted;
63
  }
64

65
  heapify(pos) {
66
    if (pos > this.tree.length) return;
67
    let leftPos = 2 * pos,
68
      rightPos = 2 * pos + 1;
69

70
    let left = this.tree[leftPos] ? this.tree[leftPos] : -Infinity;
71
    let right = this.tree[rightPos] ? this.tree[rightPos] : -Infinity,
72
      minVal = null,
73
      minIndex = null;
74

75
    if (left > right) {
76
      minVal = left;
77
      minIndex = leftPos;
78
    } else {
79
      minVal = right;
80
      minIndex = rightPos;
81
    }
82
    if (this.tree[pos] < minVal) {
83
      this.swap(pos, minIndex);
84
      this.heapify(minIndex);
85
    }
86
  }
87

88
  getTree() {
89
    return this.tree.slice(1);
90
  }
91

92
  getSize() {
93
    return this.tree.length - 1;
94
  }
95
}