-
Notifications
You must be signed in to change notification settings - Fork 22
/
heap.js
49 lines (38 loc) · 834 Bytes
/
heap.js
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
var N = 10000000;
var h = new Array(N);
function pushDown(pos, n) {
while (2 * pos + 1 < n) {
var j = 2 * pos + 1;
if (j + 1 < n && h[j + 1] > h[j])
j++;
if (h[pos] >= h[j])
break;
var t = h[pos];
h[pos] = h[j];
h[j] = t;
pos = j;
}
}
function main() {
var start = Date.now();
for (var i = 0; i < N; i++) {
h[i] = i;
}
for (var i = N / 2; i >= 0; i--)
pushDown(i, N);
var n = N;
while (n > 1) {
var t = h[0];
h[0] = h[n - 1];
h[n - 1] = t;
n--;
pushDown(0, n);
}
for (var i = 0; i < N; i++) {
if (h[i] != i) {
throw new RuntimeException("h[i] != i");
}
}
print("Done in " + (Date.now() - start));
}
main();