blob: d9ccacf4afb9b3c3b30187943f46bf7284b14f60 (
plain)
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
112
113
114
115
|
// Binary min-heap implementation used for priority queue.
// Implementation is stable, i.e. push time is considered for equal priorities
export default class Heap {
constructor() {
this.heap = [];
this.pushCount = Number.MIN_SAFE_INTEGER;
}
get length() {
return this.heap.length;
}
empty () {
this.heap = [];
return this;
}
percUp(index) {
let p;
while (index > 0 && smaller(this.heap[index], this.heap[p=parent(index)])) {
let t = this.heap[index];
this.heap[index] = this.heap[p];
this.heap[p] = t;
index = p;
}
}
percDown(index) {
let l;
while ((l=leftChi(index)) < this.heap.length) {
if (l+1 < this.heap.length && smaller(this.heap[l+1], this.heap[l])) {
l = l+1;
}
if (smaller(this.heap[index], this.heap[l])) {
break;
}
let t = this.heap[index];
this.heap[index] = this.heap[l];
this.heap[l] = t;
index = l;
}
}
push(node) {
node.pushCount = ++this.pushCount;
this.heap.push(node);
this.percUp(this.heap.length-1);
}
unshift(node) {
return this.heap.push(node);
}
shift() {
let [top] = this.heap;
this.heap[0] = this.heap[this.heap.length-1];
this.heap.pop();
this.percDown(0);
return top;
}
toArray() {
return [...this];
}
*[Symbol.iterator] () {
for (let i = 0; i < this.heap.length; i++) {
yield this.heap[i].data;
}
}
remove (testFn) {
let j = 0;
for (let i = 0; i < this.heap.length; i++) {
if (!testFn(this.heap[i])) {
this.heap[j] = this.heap[i];
j++;
}
}
this.heap.splice(j);
for (let i = parent(this.heap.length-1); i >= 0; i--) {
this.percDown(i);
}
return this;
}
}
function leftChi(i) {
return (i<<1)+1;
}
function parent(i) {
return ((i+1)>>1)-1;
}
function smaller(x, y) {
if (x.priority !== y.priority) {
return x.priority < y.priority;
}
else {
return x.pushCount < y.pushCount;
}
}
|
