优先队列性能比较,100W条数据
来源:8-4 从堆中取出元素和Sift Down
qq_萌新_4
2020-06-15
用数组队列构造的优先队列是test2,麻烦老师看一下合理不。用时20多分钟,而二分堆只用了0.28秒
public static void main(String[] args) {
test1();
System.out.println();
test2();
}
private static void test1() {
long t1 = System.nanoTime();
int n = 1000000;
MaxHeap<Integer> maxHeap = new MaxHeap<>();
Random random = new Random();
for (int i = 0; i < n; i++) {
maxHeap.add(random.nextInt(100));
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = maxHeap.extractMax();
}
for (int i = 1; i < n; i++) {
if (arr[i - 1] < arr[i]) {
throw new IllegalArgumentException("Error.");
}
}
long t2 = System.nanoTime();
System.out.println("Test MaxHeap completed." + (t2 - t1) / 1000000000.0);
}
private static void test2() {
long t1 = System.nanoTime();
int n = 1000000;
ArrayPriorityQueue<Integer> arrayPriorityQueue = new ArrayPriorityQueue<>();
Random random = new Random();
for (int i = 0; i < n; i++) {
arrayPriorityQueue.enqueue(random.nextInt(Integer.MAX_VALUE));
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = arrayPriorityQueue.dequeue();
}
for (int i = 1; i < n; i++) {
if (arr[i - 1] < arr[i]) {
throw new IllegalArgumentException("Error.");
}
}
long t2 = System.nanoTime();
System.out.println("Test arrayPriorityQueue completed." + (t2 - t1) / 1000000000.0);
}
结果:
Test MaxHeap completed.0.282107601
Test arrayPriorityQueue completed.1306.001838701
Process finished with exit code 0
写回答
1回答
-
具体代码我不看啦,我看到测试有抛异常,如果没有抛异常至少你验证的逻辑没有问题:)
继续加油!:)
042020-06-15
相似问题