Kth Largest Element in an Array LeetCode solution in JavaScript

1
// TC: O(klogk + (n-k)logk) => O(nlogk) | SC: O(k)
2
var findKthLargest = function (nums, k) {
3
  const minHeap = new MinHeap();
4

5
  // add k elements, one-by-one to heap
6
  // TC: O(klogk) | SC: O(k)
7
  for (let i = 0; i < k; i++) {
8
    minHeap.push(nums[i]);
9
  }
10

11
  // loop remaining elements
12
  // TC: O((n-k)logk) time
13
  for (let j = k; j < nums.length; j++) {
14
    // pop smaller element, and push larger element
15
    if (nums[j] > minHeap.peek()) {
16
      minHeap.pop();
17
      minHeap.push(nums[j]);
18
    }
19
    // otherwise, do nothing
20
  }
21

22
  return minHeap.peek();
23
};
24

25
class MinHeap {
26
  constructor() {
27
    this.heap = [];
28
  }
29

30
  push(node) {
31
    // add node to end of heap
32
    this.heap.push(node);
33
    // find correct position of node
34
    this.siftUp();
35
  }
36

37
  siftUp() {
38
    let currIdx = this.heap.length - 1,
39
      parentIdx = Math.floor((currIdx - 1) / 2);
40
    while (currIdx > 0 && this.heap[parentIdx] > this.heap[currIdx]) {
41
      // swap values, and set new currIdx and parentIdx
42
      this.swap(currIdx, parentIdx);
43
      currIdx = parentIdx;
44
      parentIdx = Math.floor((currIdx - 1) / 2);
45
    }
46
  }
47

48
  pop() {
49
    const min = this.heap[0];
50
    // assign top node to last node to retain complete binary tree property
51
    this.heap[0] = this.heap[this.heap.length - 1];
52
    // pop last node and find correct position of top node
53
    this.heap.pop();
54
    this.siftDown();
55
    return min;
56
  }
57

58
  siftDown() {
59
    let currIdx = 0,
60
      leftIdx = currIdx * 2 + 1,
61
      idxToSwap = leftIdx;
62
    const heapLen = this.heap.length;
63

64
    while (leftIdx < heapLen) {
65
      // calc right child node
66
      let rightIdx = leftIdx + 1;
67

68
      // set idxToSwap
69
      if (rightIdx < heapLen && this.heap[rightIdx] < this.heap[leftIdx])
70
        idxToSwap = rightIdx;
71
      else idxToSwap = leftIdx;
72

73
      // compare smaller child node to curr node
74
      if (this.heap[currIdx] <= this.heap[idxToSwap]) break;
75

76
      // otherwise, swap vals and set new currIdx and leftIdx
77
      this.swap(currIdx, idxToSwap);
78
      currIdx = idxToSwap;
79
      leftIdx = currIdx * 2 + 1;
80
    }
81
  }
82

83
  swap(i, j) {
84
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
85
  }
86

87
  peek() {
88
    return this.heap[0];
89
  }
90

91
  size() {
92
    return this.heap.length;
93
  }
94
}