优先队列性能比较,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回答

liuyubobobo

2020-06-15

具体代码我不看啦,我看到测试有抛异常,如果没有抛异常至少你验证的逻辑没有问题:)


继续加油!:)

0
4
liuyubobobo
回复
qq_萌新_4
继续加油!:)
2020-06-15
共4条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程