Repository navigation
Expand file tree
/
Copy pathMinHeap.js
More file actions
59 lines (59 loc) · 1.39 KB
/
Copy pathMinHeap.js
File metadata and controls
59 lines (59 loc) · 1.39 KB
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
/*
* 最小堆
*/
module.exports = class MinHeap {
constructor() {
this.data = [];
this.count = 0;
}
init(arr) {
this.data = arr;
this.count = arr.length;
for(let i = Math.floor(this.count/2)-1; i >= 0; i--) {
this.shiftDown(i);
}
}
shiftUp(k) {
while(k > 0 && this.data[Math.floor((k-1)/2)].wt() > this.data[k].wt()) {
this.swap(Math.floor((k-1)/2), k);
k = Math.floor((k-1)/2);
}
}
shiftDown(k) {
while(2*k+1 < this.count) {
let j = 2*k+1;
if(j+1 < this.count && this.data[j+1].wt() < this.data[j].wt()) j++;
if(this.data[k].wt() <= this.data[j].wt()) break;
this.swap(k, j);
k = j;
}
}
insert(edge) {
this.data[this.count] = edge;
this.shiftUp(this.count);
this.count++;
}
extractMin() {
if(this.count <= 0) return;
let value = this.data[0];
this.swap(0, this.count-1);
this.count--;
this.shiftDown(0);
return value;
}
getMin() {
if(this.count <= 0) return;
return this.data[0];
}
size() {
return this.count;
}
isEmpty() {
return this.count === 0;
}
swap(a, b) {
let t = this.data[a];
this.data[a] = this.data[b];
this.data[b] = t;
}
}