import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Scanner;
public class Main {
public static void main
(String[] args
) { final int N = 500000;
ArrayList<Long> values = new ArrayList<>();
for (int i = 0; i < N; ++i) {
long v
= rnd.
nextInt(Integer.
MAX_VALUE) * (1L
<< 32) + rnd.
nextInt(Integer.
MAX_VALUE); values.add(v);
}
System.
out.
println("uniform distribution"); benchmark(values);
values.clear();
for (int i = 0; i < N; ++i) {
long v
= (long) Math.
exp(rnd.
nextDouble() * 40 + 1); values.add(v);
}
System.
out.
println("exponential distribution"); benchmark(values);
}
static void benchmark(ArrayList<Long> values) {
{
long startTime
= System.
currentTimeMillis(); RadixHeap q = new RadixHeap();
for (int i = 0; i < values.size(); ++i) {
q.push(values.get(i));
}
ArrayList<Long> popped = new ArrayList<>(values.size());
while (q.size() > 0) {
popped.add(q.pop());
}
System.
out.
println("RadixHeap:" + (System.
currentTimeMillis() - startTime
)); }
{
long startTime
= System.
currentTimeMillis(); PriorityQueue<Long> q = new PriorityQueue<>();
for (int i = 0; i < values.size(); ++i) {
q.add(values.get(i));
}
ArrayList<Long> popped = new ArrayList<>(values.size());
while (q.size() > 0) {
popped.add(q.poll());
}
System.
out.
println("PriorityQueue:" + (System.
currentTimeMillis() - startTime
)); }
// verify
// Collections.sort(values);
// System.out.println(poped.equals(values));
}
static class RadixHeap {
private ArrayList<ArrayList<Long>> buf = new ArrayList<>();
private long last = 0;
private int size = 0;
RadixHeap() {
for (int i = 0; i <= 64; ++i) {
buf.add(new ArrayList<Long>());
}
}
void push(long v) {
assert (last <= v);
++size;
buf.get(bsr(v ^ last)).add(v);
}
long pop() {
if (buf.get(0).isEmpty()) {
int pos = 1;
while (buf.get(pos).isEmpty()) {
++pos;
}
long nextLast
= Long.
MAX_VALUE; for (int i = 0; i < buf.get(pos).size(); ++i) {
nextLast
= Math.
min(nextLast, buf.
get(pos
).
get(i
)); }
for (long move : buf.get(pos)) {
buf.get(bsr(move ^ nextLast)).add(move);
}
last = nextLast;
buf.get(pos).clear();
}
--size;
buf.get(0).remove(buf.get(0).size() - 1);
return last;
}
int size() {
return this.size;
}
static int bsr(long v) {
return 64 - Long.
numberOfLeadingZeros(v
); }
}
}