Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2c67b48

Browse files
authored
Ad hoc versions of MinHeap, MaxHeap, and DisjointSet (trekhleb#1117)
* Add DisjointSetMinimalistic* Add MinHeapMinimalistic and MaxHeapMinimalistic* Rename minimalistic to adhoc* Update README
1 parentac78353 commit2c67b48

File tree

8 files changed

+552
-0
lines changed

8 files changed

+552
-0
lines changed
Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
/**
2+
* The minimalistic (ad hoc) version of a DisjointSet (or a UnionFind) data structure
3+
* that doesn't have external dependencies and that is easy to copy-paste and
4+
* use during the coding interview if allowed by the interviewer (since many
5+
* data structures in JS are missing).
6+
*
7+
* Time Complexity:
8+
*
9+
* - Constructor: O(N)
10+
* - Find: O(α(N))
11+
* - Union: O(α(N))
12+
* - Connected: O(α(N))
13+
*
14+
* Where N is the number of vertices in the graph.
15+
* α refers to the Inverse Ackermann function.
16+
* In practice, we assume it's a constant.
17+
* In other words, O(α(N)) is regarded as O(1) on average.
18+
*/
19+
classDisjointSetAdhoc{
20+
/**
21+
* Initializes the set of specified size.
22+
*@param {number} size
23+
*/
24+
constructor(size){
25+
// The index of a cell is an id of the node in a set.
26+
// The value of a cell is an id (index) of the root node.
27+
// By default, the node is a parent of itself.
28+
this.roots=newArray(size).fill(0).map((_,i)=>i);
29+
30+
// Using the heights array to record the height of each node.
31+
// By default each node has a height of 1 because it has no children.
32+
this.heights=newArray(size).fill(1);
33+
}
34+
35+
/**
36+
* Finds the root of node `a`
37+
*@param {number} a
38+
*@returns {number}
39+
*/
40+
find(a){
41+
if(a===this.roots[a])returna;
42+
this.roots[a]=this.find(this.roots[a]);
43+
returnthis.roots[a];
44+
}
45+
46+
/**
47+
* Joins the `a` and `b` nodes into same set.
48+
*@param {number} a
49+
*@param {number} b
50+
*@returns {number}
51+
*/
52+
union(a,b){
53+
constaRoot=this.find(a);
54+
constbRoot=this.find(b);
55+
56+
if(aRoot===bRoot)return;
57+
58+
if(this.heights[aRoot]>this.heights[bRoot]){
59+
this.roots[bRoot]=aRoot;
60+
}elseif(this.heights[aRoot]<this.heights[bRoot]){
61+
this.roots[aRoot]=bRoot;
62+
}else{
63+
this.roots[bRoot]=aRoot;
64+
this.heights[aRoot]+=1;
65+
}
66+
}
67+
68+
/**
69+
* Checks if `a` and `b` belong to the same set.
70+
*@param {number} a
71+
*@param {number} b
72+
*/
73+
connected(a,b){
74+
returnthis.find(a)===this.find(b);
75+
}
76+
}
77+
78+
exportdefaultDisjointSetAdhoc;

‎src/data-structures/disjoint-set/README.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,11 @@ _MakeSet_ creates 8 singletons.
1919

2020
After some operations of_Union_, some sets are grouped together.
2121

22+
##Implementation
23+
24+
-[DisjointSet.js](./DisjointSet.js)
25+
-[DisjointSetAdhoc.js](./DisjointSetAdhoc.js) - The minimalistic (ad hoc) version of a DisjointSet (or a UnionFind) data structure that doesn't have external dependencies and that is easy to copy-paste and use during the coding interview if allowed by the interviewer (since many data structures in JS are missing).
26+
2227
##References
2328

2429
-[Wikipedia](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
importDisjointSetAdhocfrom'../DisjointSetAdhoc';
2+
3+
describe('DisjointSetAdhoc',()=>{
4+
it('should create unions and find connected elements',()=>{
5+
constset=newDisjointSetAdhoc(10);
6+
7+
// 1-2-5-6-7 3-8-9 4
8+
set.union(1,2);
9+
set.union(2,5);
10+
set.union(5,6);
11+
set.union(6,7);
12+
13+
set.union(3,8);
14+
set.union(8,9);
15+
16+
expect(set.connected(1,5)).toBe(true);
17+
expect(set.connected(5,7)).toBe(true);
18+
expect(set.connected(3,8)).toBe(true);
19+
20+
expect(set.connected(4,9)).toBe(false);
21+
expect(set.connected(4,7)).toBe(false);
22+
23+
// 1-2-5-6-7 3-8-9-4
24+
set.union(9,4);
25+
26+
expect(set.connected(4,9)).toBe(true);
27+
expect(set.connected(4,3)).toBe(true);
28+
expect(set.connected(8,4)).toBe(true);
29+
30+
expect(set.connected(8,7)).toBe(false);
31+
expect(set.connected(2,3)).toBe(false);
32+
});
33+
34+
it('should keep the height of the tree small',()=>{
35+
constset=newDisjointSetAdhoc(10);
36+
37+
// 1-2-6-7-9 1 3 4 5
38+
set.union(7,6);
39+
set.union(1,2);
40+
set.union(2,6);
41+
set.union(1,7);
42+
set.union(9,1);
43+
44+
expect(set.connected(1,7)).toBe(true);
45+
expect(set.connected(6,9)).toBe(true);
46+
expect(set.connected(4,9)).toBe(false);
47+
48+
expect(Math.max(...set.heights)).toBe(3);
49+
});
50+
});
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 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+
classMaxHeapAdhoc{
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+
returnthis.heap[0];
20+
}
21+
22+
poll(){
23+
if(this.heap.length===0)returnundefined;
24+
consttop=this.heap[0];
25+
this.heap[0]=this.heap[this.heap.length-1];
26+
this.heap.pop();
27+
this.heapifyDown();
28+
returntop;
29+
}
30+
31+
isEmpty(){
32+
returnthis.heap.length===0;
33+
}
34+
35+
toString(){
36+
returnthis.heap.join(',');
37+
}
38+
39+
heapifyUp(){
40+
letnodeIndex=this.heap.length-1;
41+
while(nodeIndex>0){
42+
constparentIndex=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+
letnodeIndex=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+
constleftIndex=this.getLeftChildIndex(nodeIndex);
61+
constrightIndex=this.getRightChildIndex(nodeIndex);
62+
constleft=this.leftChild(nodeIndex);
63+
constright=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+
}elseif(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+
returnMath.floor((childIndex-1)/2);
90+
}
91+
92+
hasLeftChild(parentIndex){
93+
returnthis.getLeftChildIndex(parentIndex)<this.heap.length;
94+
}
95+
96+
hasRightChild(parentIndex){
97+
returnthis.getRightChildIndex(parentIndex)<this.heap.length;
98+
}
99+
100+
leftChild(parentIndex){
101+
returnthis.heap[this.getLeftChildIndex(parentIndex)];
102+
}
103+
104+
rightChild(parentIndex){
105+
returnthis.heap[this.getRightChildIndex(parentIndex)];
106+
}
107+
108+
swap(indexOne,indexTwo){
109+
consttmp=this.heap[indexTwo];
110+
this.heap[indexTwo]=this.heap[indexOne];
111+
this.heap[indexOne]=tmp;
112+
}
113+
}
114+
115+
exportdefaultMaxHeapAdhoc;
Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
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+
classMinHeapAdhoc{
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+
returnthis.heap[0];
20+
}
21+
22+
poll(){
23+
if(this.heap.length===0)returnundefined;
24+
consttop=this.heap[0];
25+
this.heap[0]=this.heap[this.heap.length-1];
26+
this.heap.pop();
27+
this.heapifyDown();
28+
returntop;
29+
}
30+
31+
isEmpty(){
32+
returnthis.heap.length===0;
33+
}
34+
35+
toString(){
36+
returnthis.heap.join(',');
37+
}
38+
39+
heapifyUp(){
40+
letnodeIndex=this.heap.length-1;
41+
while(nodeIndex>0){
42+
constparentIndex=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+
letnodeIndex=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+
constleftIndex=this.getLeftChildIndex(nodeIndex);
63+
constrightIndex=this.getRightChildIndex(nodeIndex);
64+
constleft=this.leftChild(nodeIndex);
65+
constright=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+
}elseif(this.hasLeftChild(nodeIndex)){
76+
this.swap(leftIndex,nodeIndex);
77+
nodeIndex=leftIndex;
78+
}
79+
}
80+
}
81+
82+
getLeftChildIndex(parentIndex){
83+
return2*parentIndex+1;
84+
}
85+
86+
getRightChildIndex(parentIndex){
87+
return2*parentIndex+2;
88+
}
89+
90+
getParentIndex(childIndex){
91+
returnMath.floor((childIndex-1)/2);
92+
}
93+
94+
hasLeftChild(parentIndex){
95+
returnthis.getLeftChildIndex(parentIndex)<this.heap.length;
96+
}
97+
98+
hasRightChild(parentIndex){
99+
returnthis.getRightChildIndex(parentIndex)<this.heap.length;
100+
}
101+
102+
leftChild(parentIndex){
103+
returnthis.heap[this.getLeftChildIndex(parentIndex)];
104+
}
105+
106+
rightChild(parentIndex){
107+
returnthis.heap[this.getRightChildIndex(parentIndex)];
108+
}
109+
110+
swap(indexOne,indexTwo){
111+
consttmp=this.heap[indexTwo];
112+
this.heap[indexTwo]=this.heap[indexOne];
113+
this.heap[indexOne]=tmp;
114+
}
115+
}
116+
117+
exportdefaultMinHeapAdhoc;

‎src/data-structures/heap/README.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -58,6 +58,11 @@ Where:
5858

5959
>In this repository, the[MaxHeap.js](./MaxHeap.js) and[MinHeap.js](./MinHeap.js) are examples of the**Binary** heap.
6060
61+
##Implementation
62+
63+
-[MaxHeap.js](./MaxHeap.js) and[MinHeap.js](./MinHeap.js)
64+
-[MaxHeapAdhoc.js](./MaxHeapAdhoc.js) and[MinHeapAdhoc.js](./MinHeapAdhoc.js) - The minimalistic (ad hoc) version of a MinHeap/MaxHeap data structure that doesn't have external dependencies and that is easy to copy-paste and use during the coding interview if allowed by the interviewer (since many data structures in JS are missing).
65+
6166
##References
6267

6368
-[Wikipedia](https://en.wikipedia.org/wiki/Heap_(data_structure))

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp