blob: 0bacadceb82afc649c250a9e9242e3d7cc97c08d (
plain) (
blame)
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
|
export default class BinaryHeap<T> {
private content: T[] = [];
constructor(private scoreFunction: (node: T) => number) {}
sinkDown(idx: number) {
const node = this.content[idx];
while (idx > 0) {
const parentN = ((idx + 1) >> 1) - 1;
const parent = this.content[parentN];
if (this.scoreFunction(node) < this.scoreFunction(parent)) {
this.content[parentN] = node;
this.content[idx] = parent;
idx = parentN; // TODO: Optimize
} else {
break;
}
}
}
bubbleUp(idx: number) {
const length = this.content.length;
const node = this.content[idx];
const score = this.scoreFunction(node);
while (true) {
const child2N = (idx + 1) << 1;
const child1N = child2N - 1;
let swap = null;
let child1Score = 0;
if (child1N < length) {
const child1 = this.content[child1N];
child1Score = this.scoreFunction(child1);
if (child1Score < score) {
swap = child1N;
}
}
if (child2N < length) {
const child2 = this.content[child2N];
const child2Score = this.scoreFunction(child2);
if (child2Score < (swap === null ? score : child1Score)) {
swap = child2N;
}
}
if (swap !== null) {
this.content[idx] = this.content[swap];
this.content[swap] = node;
idx = swap; // TODO: Optimize
} else {
break;
}
}
}
push(node: T) {
this.content.push(node);
this.sinkDown(this.content.length - 1);
}
pop(): T | null {
if (this.content.length === 0) {
return null;
}
const result = this.content[0];
const end = this.content.pop()!;
if (this.content.length > 0) {
this.content[0] = end;
this.bubbleUp(0);
}
return result;
}
remove(node: T) {
if (this.content.length === 0) {
return;
}
const i = this.content.indexOf(node);
const end = this.content.pop()!;
if (i < this.content.length) {
this.content[i] = end;
if (this.scoreFunction(end) < this.scoreFunction(node)) {
this.sinkDown(i);
} else {
this.bubbleUp(i);
}
}
}
size(): number {
return this.content.length;
}
rescoreElement(node: T) {
this.sinkDown(this.content.indexOf(node));
}
}
|
