Number of Orders in the Backlog LeetCode solution in JavaScript

1
var getNumberOfBacklogOrders = function (orders) {
2
  const buyHeap = new Heap((child, parent) => child.price > parent.price);
3
  const sellHeap = new Heap((child, parent) => child.price < parent.price);
4

5
  for (let [price, amount, orderType] of orders) {
6
    // sell
7
    if (orderType) {
8
      // while there are amount to be decremented from the sell,
9
      // orders to in the buy backlog, and the price of the largest
10
      // price is greater than the sell price decrement the
11
      // amount of the order with the largest price by the amount
12
      while (amount > 0 && buyHeap.peak() && buyHeap.peak().price >= price) {
13
        if (buyHeap.peak().amount > amount) {
14
          buyHeap.peak().amount -= amount;
15
          amount = 0;
16
        } else {
17
          amount -= buyHeap.pop().amount;
18
        }
19
      }
20

21
      // if there is any amount left, add it to the sale backlog
22
      if (amount) {
23
        sellHeap.push({ price, amount });
24
      }
25

26
      // buy
27
    } else {
28
      // while there are amount to be decremented from the buy,
29
      // orders to in the sell backlog, and the price of the smallest
30
      // price is less than the buy price decrement the
31
      // amount of the order with the smallest price by the amount
32
      while (amount > 0 && sellHeap.peak() && sellHeap.peak().price <= price) {
33
        if (sellHeap.peak().amount > amount) {
34
          sellHeap.peak().amount -= amount;
35
          amount = 0;
36
        } else {
37
          amount -= sellHeap.pop().amount;
38
        }
39
      }
40

41
      // if there is any amount left, add it to the buy backlog
42
      if (amount) {
43
        buyHeap.push({ price, amount });
44
      }
45
    }
46
  }
47

48
  // total all of the amounts in both backlogs and return the result
49
  let accumultiveAmount = 0;
50
  for (const { amount } of buyHeap.store) {
51
    accumultiveAmount += amount;
52
  }
53
  for (const { amount } of sellHeap.store) {
54
    accumultiveAmount += amount;
55
  }
56
  return accumultiveAmount % 1000000007;
57
};
58

59
class Heap {
60
  constructor(fn) {
61
    this.store = [];
62
    this.fn = fn;
63
  }
64

65
  peak() {
66
    return this.store[0];
67
  }
68

69
  size() {
70
    return this.store.length;
71
  }
72

73
  pop() {
74
    if (this.store.length < 2) {
75
      return this.store.pop();
76
    }
77
    const result = this.store[0];
78
    this.store[0] = this.store.pop();
79
    this.heapifyDown(0);
80
    return result;
81
  }
82

83
  push(val) {
84
    this.store.push(val);
85
    this.heapifyUp(this.store.length - 1);
86
  }
87

88
  heapifyUp(child) {
89
    while (child) {
90
      const parent = Math.floor((child - 1) / 2);
91
      if (this.shouldSwap(child, parent)) {
92
        [this.store[child], this.store[parent]] = [
93
          this.store[parent],
94
          this.store[child],
95
        ];
96
        child = parent;
97
      } else {
98
        return child;
99
      }
100
    }
101
  }
102

103
  heapifyDown(parent) {
104
    while (true) {
105
      let [child, child2] = [1, 2]
106
        .map((x) => parent * 2 + x)
107
        .filter((x) => x < this.size());
108
      if (this.shouldSwap(child2, child)) {
109
        child = child2;
110
      }
111
      if (this.shouldSwap(child, parent)) {
112
        [this.store[child], this.store[parent]] = [
113
          this.store[parent],
114
          this.store[child],
115
        ];
116
        parent = child;
117
      } else {
118
        return parent;
119
      }
120
    }
121
  }
122

123
  shouldSwap(child, parent) {
124
    return child && this.fn(this.store[child], this.store[parent]);
125
  }
126
}