-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeap.bk.js
More file actions
76 lines (71 loc) · 2.1 KB
/
Heap.bk.js
File metadata and controls
76 lines (71 loc) · 2.1 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
class Heap {
constructor(compare, array) {
this.compare = compare;
this.tree = [0];
this.length = 0;
if (array) {
for (const val of array) {
this.push(val);
}
}
}
push(val) {
// console.log();
// console.log("push:", { val });
if (this.tree.length == 1) {
this.tree.push(val);
}
else {
const last = this.tree.length;
let i = last, p = Math.trunc(i / 2);
while (i > 1 && this.compare(val, this.tree[p])) {
this.tree[i] = this.tree[p];
i = p;
p = Math.trunc(i / 2);
}
this.tree[i] = val;
}
this.length++;
}
top() {
return this.tree[1];
}
pop() {
this.length--;
const top = this.tree[1];
// const most = this.compare(1, 2) ? Infinity : -Infinity;
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 = ri < this.tree.length ? this.tree[ri] : most;
const lval = this.tree[li], rval = this.tree[ri];
// if (this.compare(last, lval) && this.compare(last, rval)) {
if (this.compare(last, lval) && (rval == undefined || this.compare(last, rval))) {
break;
}
else {
// if (this.compare(lval, rval)) {
if (rval == undefined || this.compare(lval, rval)) {
this.tree[i] = lval;
i = li;
}
else {
this.tree[i] = rval;
i = ri;
}
li = i * 2, ri = li + 1;
}
}
// console.log(this.tree);
// const last = this.tree.pop();
this.tree.pop();
if (i != this.tree.length) {
this.tree[i] = last;
}
return top;
}
isEmpty() {
return this.length == 0;
}
}
exports.Heap = Heap;