8000 binary heaps completed and added and added string problems to index · yashkathe/DSA-with-Javascript@25219d7 · GitHub
[go: up one dir, main page]
Skip to content

Commit 25219d7

Browse files
yashkatheyashkathe
committed
binary heaps completed and added and added string problems to index
1 parent f75e52e commit 25219d7

File tree

12 files changed

+128
8000 -9
lines changed

12 files changed

+128
-9
lines changed

‎A10 Binary Heaps/binary-heaps.js

Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
class MaxBinaryHeap {
2+
constructor() {
3+
this.values = [];
4+
}
5+
6+
insert(element) {
7+
this.values.push(element);
8+
this.bubbleUp();
9+
}
10+
11+
bubbleUp() {
12+
let idx = this.values.length - 1;
13+
const element = this.values[ idx ];
14+
15+
while(idx > 0) {
16+
let parentIdx = Math.floor((idx - 1) / 2);
17+
let parent = this.values[ parentIdx ];
18+
19+
if(element <= parent) break;
20+
21+
// else : swapp
22+
this.values[ parentIdx ] = element;
23+
this.values[ idx ] = parent;
24+
25+
idx = parentIdx;
26+
27+
}
28+
29+
}
30+
31+
extractMax() {
32+
33+
const max = this.values[ 0 ];
34+
const end = this.values.pop();
35+
36+
if(this.values.length > 0) {
37+
this.values[ 0 ] = end;
38+
this.sinkDown();
39+
}
40+
41+
return max;
42+
}
43+
44+
sinkDown() {
45+
46+
let idx = 0; // because sinking down will start at 0
47+
48+
const length = this.values.length;
49+
const element = this.values[ 0 ];
50+
51+
while(true) {
52+
53+
let leftChildIdx = 2 * idx + 1;
54+
let rightChildIdx = 2 * idx + 2;
55+
56+
let leftChild, rightChild;
57+
let swap = null; // to keep checks of swap
58+
59+
// check if there is a children and its not out of bound
60+
if(leftChildIdx < length) {
61+
62+
leftChild = this.values[ leftChildIdx ];
63+
if(leftChild > element) {
64+
swap = leftChildIdx;
65+
}
66+
}
67+
68+
if(rightChildIdx < length) {
69+
70+
rightChild = this.values[ rightChildIdx ];
71+
if((
72+
swap === null && rightChildIdx > element) ||
73+
(swap !== null && rightChild > leftChild)
74+
) {
75+
swap = rightChildIdx;
76+
}
77+
}
78+
79+
if(swap === null) break;
80+
81+
// swapping values
82+
this.values[ idx ] = this.values[ swap ];
83+
this.values[ swap ] = element;
84+
idx = swap;
85+
}
86+
}
87+
}
88+
89+
90+
let heap = new MaxBinaryHeap();
91+
92+
heap.insert(41);
93+
heap.insert(39);
94+
heap.insert(33);
A3E2 95+
heap.insert(18);
96+
heap.insert(27);
97+
heap.insert(12);
98+
heap.insert(55);
99+
100+
console.log(heap.values);
101+
102+
console.log(heap.extractMax())
103+
console.log(heap.extractMax())
104+
console.log(heap.extractMax())
105+
console.log(heap.extractMax())
106+
console.log(heap.extractMax())
107+
console.log(heap.extractMax())
108+
console.log(heap.extractMax())
109+
110+
console.log(heap.values)
111+
112+
/*
113+
114+
[55,41.39,33,18,27,12]
115+
0 1 2 3 4 5 6
116+
117+
*/

‎B1 LEETCODE-Easy/9.js

Lines changed: 0 additions & 8 deletions
This file was deleted.

‎B1 LEETCODE-Easy/README.md renamed to ‎B1 LEETCODE-Easy/README.archive.md

File renamed without changes.

‎B1 LEETCODE-Easy/4.ts renamed to ‎B1 LEETCODE-Easy/String/defanging-ip.ts

File renamed without changes.

‎B1 LEETCODE-Easy/8.ts renamed to ‎B1 LEETCODE-Easy/String/goal-parser.ts

File renamed without changes.

‎B1 LEETCODE-Easy/7.ts renamed to ‎B1 LEETCODE-Easy/String/jewels-and-stones.ts

File renamed without changes.

‎B1 LEETCODE-Easy/6.ts renamed to ‎B1 LEETCODE-Easy/String/max-words-in-sentence.ts

File renamed without changes.

‎B1 LEETCODE-Easy/2.js renamed to ‎B1 LEETCODE-Easy/String/palindrome-number.js

File renamed without changes.

‎B1 LEETCODE-Easy/3.js renamed to ‎B1 LEETCODE-Easy/String/roman-to-integer.js

File renamed without changes.

‎B1 LEETCODE-Easy/1.js renamed to ‎B1 LEETCODE-Easy/String/two-sum.js

File renamed without changes.

0 commit comments

Comments
 (0)
0