Java TreeSet 使用的内存是否少于 PriorityQueue？

Question

我正在这样做 Question 并首先使用 PriorityQueue 解决了它:-

public ArrayList<Integer> solve(int A, int B, int C, int D) {
    PriorityQueue<Integer> q = new PriorityQueue<>();
    q.add(A);
    q.add(B);
    q.add(C);
    ArrayList<Integer> list = new ArrayList<>();
    while(list.size() < D){
        int val = q.poll();
        if(list.size() == 0 || list.get(list.size() - 1) != val)
        list.add(val);
        q.add(val*A);
        q.add(val*B);
        q.add(val*C);
    }

    list.sort(null);
    return list;
}

但它给出了 java.lang.OutOfMemoryError: Java 堆 space 错误。
将PriorityQueue换成TreeSet后，方案被采纳：-

 public ArrayList<Integer> solve(int A, int B, int C, int D) {
    ArrayList<Integer> res = new ArrayList<>() ;

    TreeSet<Integer> set = new TreeSet<>() ;
    set.add(A) ;
    set.add(B) ;
    set.add(C) ;

    for(int i = 0; i < D; i++) {
        int temp = set.first() ;
        set.remove(temp) ;
        res.add(temp) ;

        set.add(temp*A) ;
        set.add(temp*B) ;
        set.add(temp*C) ;

    }
    return res ;
}

Answer 1

它基本上与使用的内存量无关，只是你使用 PriorityQueue 的程序永远不会结束，一遍又一遍地向 PriorityQueue 添加元素。

它不会结束，因为你的条件 if(list.size() == 0 || list.get(list.size() - 1) != val) - 它永远不会满足，因此检查 list 大小（永远不会改变）的 while 循环总是正确的，所以每个循环执行从队列中取出 1 个元素，然后向其中添加 3 个元素。

Answer 2

这与数据结构无关。第一种情况的参数组合可能导致此语句永远不会为真：

if(list.size() == 0 || list.get(list.size() - 1) != val)

这意味着循环永远不会终止，对象 q 会一直增长，直到运行内存不足。例如尝试调用：

solve(1,1,2,5)

两种数据结构之间的内存差异在这种情况下没有影响。需要注意与随机访问和 next/previous 指针相关的一些差异，但与此处无关。

Java TreeSet 使用的内存是否少于 PriorityQueue？

Does Java TreeSet uses less memory than PriorityQueue?

java

priority-queue

treeset