-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapWithPercolate.js
More file actions
111 lines (101 loc) · 2.93 KB
/
Copy pathHeapWithPercolate.js
File metadata and controls
111 lines (101 loc) · 2.93 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
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
class HeapWithPercolate {
constructor(compare, array) {
this.compare = compare;
this.tree = [0];
this.length = 0;
this.map = new Map();
if (array) {
for (const val of array) {
this.push(val);
}
}
}
push(val) {
if (this.tree.length == 1) {
this.tree.push(val);
this.map.set(val, 1);
}
else {
const last = this.tree.length;
let i = last, p = Math.trunc(i / 2);
while (i > 1 && this.compare(val, this.tree[p])) {
const val2 = this.tree[p];
this.tree[i] = val2;
this.map.set(val2, i)
i = p;
p = Math.trunc(i / 2);
}
this.tree[i] = val;
this.map.set(val, i);
}
this.length++;
}
top() {
return this.tree[1];
}
pop() {
this.length--;
const top = this.tree[1];
this.map.delete(top);
const last = this.tree[this.tree.length - 1];
let i = 1, li = i * 2, ri = li + 1;
while (li < this.tree.length) {
const lval = this.tree[li], rval = this.tree[ri];
if (this.compare(last, lval) && (rval == undefined || this.compare(last, rval))) {
break;
}
else {
if (rval == undefined || this.compare(lval, rval)) {
this.tree[i] = lval;
this.map.set(lval, i);
i = li;
}
else {
this.tree[i] = rval;
this.map.set(rval, i);
i = ri;
}
li = i * 2, ri = li + 1;
}
}
this.tree.pop();
if (i != this.tree.length) {
this.tree[i] = last;
this.map.set(last, i);
}
return top;
}
changeDown(val) {
let i = this.map.get(val);
let li = i * 2, ri = li + 1;
while (li < this.tree.length) {
const lval = this.tree[li], rval = this.tree[ri];
if (!this.compare(lval, val) && (rval == undefined || !this.compare(rval, val))) {
break;
}
else {
if (rval == undefined || this.compare(lval, rval)) {
this.tree[i] = lval;
this.map.set(lval, i);
i = li;
}
else {
this.tree[i] = rval;
this.map.set(rval, i);
i = ri;
}
li = i * 2, ri = li + 1;
}
}
this.tree[i] = val;
this.map.set(val, i);
}
isEmpty() {
return this.length == 0;
}
update(i, val) {
this.tree[i] = val;
this.map.set(val, i);
}
}
exports.HeapWithPercolate = HeapWithPercolate;