Skip to content

Commit dfb704c

Browse files
BarklimBarklim
Barklim
authored and
Barklim
committed
add minheap examples
1 parent 1667437 commit dfb704c

8 files changed

+405
-6
lines changed

‎0215-kth-largest-element-in-an-array.js

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,3 +16,33 @@
1616
var findKthLargest = function(nums, k) {
1717
return nums.sort((a, b) => a - b)[nums.length - k];
1818
};
19+
20+
// var findKthLargest = function(nums, k) {
21+
22+
// const min_heap = new MinHeapAdhoc();
23+
24+
// for (const num of nums) {
25+
// min_heap.add(num)
26+
// if (min_heap.heap.length > k) {
27+
// min_heap.poll();
28+
// }
29+
// }
30+
31+
// return min_heap.heap[0]
32+
// };
33+
34+
35+
// var findKthLargest = function(nums, k) {
36+
37+
// const max_heap = new MaxHeapAdhoc();
38+
39+
// for (const num of nums) {
40+
// max_heap.add(num)
41+
// }
42+
43+
// for (let i = 0; i < k - 1; i++) {
44+
// max_heap.poll();
45+
// }
46+
47+
// return max_heap.heap[0]
48+
// };

‎0347-top-k-frequent-elements.js

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,3 +52,25 @@ var topKFrequent = function(nums, k) {
5252
// }
5353
// }
5454
// };
55+
56+
// var topKFrequent = function(nums, k) {
57+
// const freqMap = new Map();
58+
59+
// // Подсчёт частоты элементов
60+
// for (const num of nums) {
61+
// freqMap.set(num, (freqMap.get(num) || 0) + 1);
62+
// }
63+
64+
// const minHeap = new MinHeapAdhoc();
65+
66+
// // Заполняем хипу
67+
// for (const [num, freq] of freqMap.entries()) {
68+
// minHeap.add([freq, num]);
69+
// if (minHeap.heap.length > k) {
70+
// minHeap.poll();
71+
// }
72+
// }
73+
74+
// // Извлекаем k самых частых элементов
75+
// return minHeap.heap.map(item => item[1]);
76+
// };

‎0703-kth-largest-element-in-a-stream.js

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,3 +46,28 @@ KthLargest.prototype.add = function(val) {
4646

4747
return this.main.front().element;
4848
};
49+
50+
// var KthLargest = function(k, nums) {
51+
// this.k = k;
52+
// this.min_heap = new MinHeapAdhoc();
53+
54+
// // Добавляем элементы в хипу и оставляем только k наибольших
55+
// for (const num of nums) {
56+
// this.min_heap.add(num);
57+
// if (this.min_heap.heap.length > k) {
58+
// this.min_heap.poll();
59+
// }
60+
// }
61+
// };
62+
63+
// /**
64+
// * @param {number} val
65+
// * @return {number}
66+
// */
67+
// KthLargest.prototype.add = function(val) {
68+
// this.min_heap.add(val);
69+
// if (this.min_heap.heap.length > this.k) {
70+
// this.min_heap.poll();
71+
// }
72+
// return this.min_heap.heap[0]; // k-й по величине элемент
73+
// };

‎dStructure/MaxHeapAdhoc.js

Lines changed: 114 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,114 @@
1+
/**
2+
* The minimalistic (ad hoc) version of a MaxHeap data structure that doesn't have
3+
* external dependencies and that is easy to copy-paste and use during the
4+
* coding interview if allowed by the interviewer (since many data
5+
* structures in JS are missing).
6+
*/
7+
class MaxHeapAdhoc {
8+
constructor(heap = []) {
9+
this.heap = [];
10+
heap.forEach(this.add);
11+
}
12+
13+
add(num) {
14+
this.heap.push(num);
15+
this.heapifyUp();
16+
}
17+
18+
peek() {
19+
return this.heap[0];
20+
}
21+
22+
poll() {
23+
if (this.heap.length === 0) return undefined;
24+
const top = this.heap[0];
25+
this.heap[0] = this.heap[this.heap.length - 1];
26+
this.heap.pop();
27+
this.heapifyDown();
28+
return top;
29+
}
30+
31+
isEmpty() {
32+
return this.heap.length === 0;
33+
}
34+
35+
toString() {
36+
return this.heap.join(',');
37+
}
38+
39+
heapifyUp() {
40+
let nodeIndex = this.heap.length - 1;
41+
while (nodeIndex > 0) {
42+
const parentIndex = this.getParentIndex(nodeIndex);
43+
if (this.heap[parentIndex] >= this.heap[nodeIndex]) break;
44+
this.swap(parentIndex, nodeIndex);
45+
nodeIndex = parentIndex;
46+
}
47+
}
48+
49+
heapifyDown() {
50+
let nodeIndex = 0;
51+
52+
while (
53+
(
54+
this.hasLeftChild(nodeIndex) && this.heap[nodeIndex] < this.leftChild(nodeIndex)
55+
)
56+
|| (
57+
this.hasRightChild(nodeIndex) && this.heap[nodeIndex] < this.rightChild(nodeIndex)
58+
)
59+
) {
60+
const leftIndex = this.getLeftChildIndex(nodeIndex);
61+
const rightIndex = this.getRightChildIndex(nodeIndex);
62+
const left = this.leftChild(nodeIndex);
63+
const right = this.rightChild(nodeIndex);
64+
65+
if (this.hasLeftChild(nodeIndex) && this.hasRightChild(nodeIndex)) {
66+
if (left >= right) {
67+
this.swap(leftIndex, nodeIndex);
68+
nodeIndex = leftIndex;
69+
} else {
70+
this.swap(rightIndex, nodeIndex);
71+
nodeIndex = rightIndex;
72+
}
73+
} else if (this.hasLeftChild(nodeIndex)) {
74+
this.swap(leftIndex, nodeIndex);
75+
nodeIndex = leftIndex;
76+
}
77+
}
78+
}
79+
80+
getLeftChildIndex(parentIndex) {
81+
return (2 * parentIndex) + 1;
82+
}
83+
84+
getRightChildIndex(parentIndex) {
85+
return (2 * parentIndex) + 2;
86+
}
87+
88+
getParentIndex(childIndex) {
89+
return Math.floor((childIndex - 1) / 2);
90+
}
91+
92+
hasLeftChild(parentIndex) {
93+
return this.getLeftChildIndex(parentIndex) < this.heap.length;
94+
}
95+
96+
hasRightChild(parentIndex) {
97+
return this.getRightChildIndex(parentIndex) < this.heap.length;
98+
}
99+
100+
leftChild(parentIndex) {
101+
return this.heap[this.getLeftChildIndex(parentIndex)];
102+
}
103+
104+
rightChild(parentIndex) {
105+
return this.heap[this.getRightChildIndex(parentIndex)];
106+
}
107+
108+
swap(indexOne, indexTwo) {
109+
const tmp = this.heap[indexTwo];
110+
this.heap[indexTwo] = this.heap[indexOne];
111+
this.heap[indexOne] = tmp;
112+
}
113+
}
114+

‎dStructure/MinHeapAdhoc.js

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
/**
2+
* The minimalistic (ad hoc) version of a MinHeap data structure that doesn't have
3+
* external dependencies and that is easy to copy-paste and use during the
4+
* coding interview if allowed by the interviewer (since many data
5+
* structures in JS are missing).
6+
*/
7+
class MinHeapAdhoc {
8+
constructor(heap = []) {
9+
this.heap = [];
10+
heap.forEach(this.add);
11+
}
12+
13+
add(num) {
14+
this.heap.push(num);
15+
this.heapifyUp();
16+
}
17+
18+
peek() {
19+
return this.heap[0];
20+
}
21+
22+
poll() {
23+
if (this.heap.length === 0) return undefined;
24+
const top = this.heap[0];
25+
this.heap[0] = this.heap[this.heap.length - 1];
26+
this.heap.pop();
27+
this.heapifyDown();
28+
return top;
29+
}
30+
31+
isEmpty() {
32+
return this.heap.length === 0;
33+
}
34+
35+
toString() {
36+
return this.heap.join(',');
37+
}
38+
39+
heapifyUp() {
40+
let nodeIndex = this.heap.length - 1;
41+
while (nodeIndex > 0) {
42+
const parentIndex = this.getParentIndex(nodeIndex);
43+
if (this.heap[parentIndex] <= this.heap[nodeIndex]) break;
44+
this.swap(parentIndex, nodeIndex);
45+
nodeIndex = parentIndex;
46+
}
47+
}
48+
49+
heapifyDown() {
50+
let nodeIndex = 0;
51+
52+
while (
53+
(
54+
this.hasLeftChild(nodeIndex)
55+
&& this.heap[nodeIndex] > this.leftChild(nodeIndex)
56+
)
57+
|| (
58+
this.hasRightChild(nodeIndex)
59+
&& this.heap[nodeIndex] > this.rightChild(nodeIndex)
60+
)
61+
) {
62+
const leftIndex = this.getLeftChildIndex(nodeIndex);
63+
const rightIndex = this.getRightChildIndex(nodeIndex);
64+
const left = this.leftChild(nodeIndex);
65+
const right = this.rightChild(nodeIndex);
66+
67+
if (this.hasLeftChild(nodeIndex) && this.hasRightChild(nodeIndex)) {
68+
if (left <= right) {
69+
this.swap(leftIndex, nodeIndex);
70+
nodeIndex = leftIndex;
71+
} else {
72+
this.swap(rightIndex, nodeIndex);
73+
nodeIndex = rightIndex;
74+
}
75+
} else if (this.hasLeftChild(nodeIndex)) {
76+
this.swap(leftIndex, nodeIndex);
77+
nodeIndex = leftIndex;
78+
}
79+
}
80+
}
81+
82+
getLeftChildIndex(parentIndex) {
83+
return 2 * parentIndex + 1;
84+
}
85+
86+
getRightChildIndex(parentIndex) {
87+
return 2 * parentIndex + 2;
88+
}
89+
90+
getParentIndex(childIndex) {
91+
return Math.floor((childIndex - 1) / 2);
92+
}
93+
94+
hasLeftChild(parentIndex) {
95+
return this.getLeftChildIndex(parentIndex) < this.heap.length;
96+
}
97+
98+
hasRightChild(parentIndex) {
99+
return this.getRightChildIndex(parentIndex) < this.heap.length;
100+
}
101+
102+
leftChild(parentIndex) {
103+
return this.heap[this.getLeftChildIndex(parentIndex)];
104+
}
105+
106+
rightChild(parentIndex) {
107+
return this.heap[this.getRightChildIndex(parentIndex)];
108+
}
109+
110+
swap(indexOne, indexTwo) {
111+
const tmp = this.heap[indexTwo];
112+
this.heap[indexTwo] = this.heap[indexOne];
113+
this.heap[indexOne] = tmp;
114+
}
115+
}

‎example/7.Tries/0208.js

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -33,4 +33,12 @@ Trie.prototype.startsWith = function(prefix) {
3333
* obj.insert(word)
3434
* var param_2 = obj.search(word)
3535
* var param_3 = obj.startsWith(prefix)
36-
*/
36+
*/
37+
38+
const trie = new Trie();
39+
trie.insert("apple");
40+
trie.search("apple"); // return True
41+
trie.search("app"); // return False
42+
trie.startsWith("app"); // return True
43+
trie.insert("app");
44+
trie.search("app");

‎example/8.Heap/0703.js

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -3,19 +3,16 @@
33
* @param {number[]} nums
44
*/
55
var KthLargest = function(k, nums) {
6-
6+
77
};
88

99
/**
1010
* @param {number} val
1111
* @return {number}
1212
*/
1313
KthLargest.prototype.add = function(val) {
14-
15-
};
1614

17-
var obj = new KthLargest(k, nums)
18-
var param_1 = obj.add(val)
15+
};
1916

2017
const kthLargest = new KthLargest(3, [4, 5, 8, 2]);
2118
kthLargest.add(3); // return 4
@@ -24,8 +21,13 @@ kthLargest.add(10); // return 5
2421
kthLargest.add(9); // return 8
2522
kthLargest.add(4); // return 8
2623

24+
console.log(kthLargest);
25+
2726
const kthLargest2 = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
2827
kthLargest2.add(2); // return 7
2928
kthLargest2.add(10); // return 7
3029
kthLargest2.add(9); // return 7
3130
kthLargest2.add(9); // return 8
31+
32+
console.log(kthLargest2);
33+

0 commit comments

Comments
 (0)