-
Notifications
You must be signed in to change notification settings - Fork 118
/
Copy pathKth Largest Element in an Array.js
93 lines (78 loc) · 2.56 KB
/
Kth Largest Element in an Array.js
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
92
93
// TC: O(klogk + (n-k)logk) => O(nlogk) | SC: O(k)
var findKthLargest = function(nums, k) {
const minHeap = new MinHeap();
// add k elements, one-by-one to heap
// TC: O(klogk) | SC: O(k)
for (let i = 0; i < k; i++) {
minHeap.push(nums[i]);
}
// loop remaining elements
// TC: O((n-k)logk) time
for (let j = k; j < nums.length; j++) {
// pop smaller element, and push larger element
if (nums[j] > minHeap.peek()) {
minHeap.pop();
minHeap.push(nums[j]);
}
// otherwise, do nothing
}
return minHeap.peek();
};
class MinHeap {
constructor() {
this.heap = [];
}
push(node) {
// add node to end of heap
this.heap.push(node);
// find correct position of node
this.siftUp();
}
siftUp() {
let currIdx = this.heap.length - 1,
parentIdx = Math.floor((currIdx - 1) / 2);
while (currIdx > 0 && this.heap[parentIdx] > this.heap[currIdx]) {
// swap values, and set new currIdx and parentIdx
this.swap(currIdx, parentIdx);
currIdx = parentIdx;
parentIdx = Math.floor((currIdx - 1) / 2);
}
}
pop() {
const min = this.heap[0];
// assign top node to last node to retain complete binary tree property
this.heap[0] = this.heap[this.heap.length - 1];
// pop last node and find correct position of top node
this.heap.pop();
this.siftDown();
return min;
}
siftDown() {
let currIdx = 0,
leftIdx = currIdx * 2 + 1,
idxToSwap = leftIdx;
const heapLen = this.heap.length;
while (leftIdx < heapLen) {
// calc right child node
let rightIdx = leftIdx + 1;
// set idxToSwap
if (rightIdx < heapLen && this.heap[rightIdx] < this.heap[leftIdx]) idxToSwap = rightIdx;
else idxToSwap = leftIdx;
// compare smaller child node to curr node
if (this.heap[currIdx] <= this.heap[idxToSwap]) break;
// otherwise, swap vals and set new currIdx and leftIdx
this.swap(currIdx, idxToSwap);
currIdx = idxToSwap;
leftIdx = currIdx * 2 + 1;
}
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
}