2

I am trying to implement a priority queue of my class type BBNode, but it doesn't seem to sift up the new nodes the way I expect it. Rather than have the smallest be at the head of the queue (how it works now), I want the largest to be there, but I can't figure out how to make this work. Here's my BBNode class.

public class BBNode implements Comparable<BBNode>{
    public int level; //level on the tree
    public int value; //value up to that node
    public int weight; //weight up to that node
    public double bound; //bound of that node

    //...constructors
    public int compareTo(BBNode node){
        if(this.bound > node.bound) return -1;
        if(this.bound < node.bound) return 1;
        return 0;
    }
}

And here's where I use the PQ.

PriorityQueue<BBNode> pq = new PriorityQueue<BBNode>();
//..other variables
while(pq.peek() != null){
  v = pq.poll();
  //System.out.println(v.weight + " " + v.value + " " + v.bound);
  if(v.bound >= bestVal && v.level < sortedItems.length-1){
     //left branch: take the next item
     u.level = v.level+1;
     u.weight = v.weight + sortedItems[u.level].weight;
     u.value = v.value + sortedItems[u.level].value;
     u.bound = bound(u);
     //System.out.println(u.bound);
     if(u.bound > bestVal){
        pq.add(u);
        System.out.println("adding " + u.bound);
        System.out.println("top of pq is " + pq.peek().bound);
     }
     if(u.weight <= maxWt && u.value > bestVal){
        bestVal = u.value;
        bestWt = u.weight;
        //System.out.println(bestVal + " " + bestWt);
        takeList[arrIdx++] = sortedItems[u.level].item+1;
     }
     //right branch: don't take the next item
     u.weight = v.weight;
     u.value = v.value;
     u.bound = bound(u);
     if(u.bound > bestVal){
        pq.add(u);
        System.out.println("adding " + u.bound);
        System.out.println("top of pq is " + pq.peek().bound);
     }
  }
}

Sorry the formatting at the end sucks. The last bracket corresponds to the while loop.

I've also tried switching around the -1 and 1 in the compare method, and I've also tried implementing a Comparator, but with the same results.

Any help is appreciated :)

4

2 回答 2

3

可能发生的情况是您正在修改bound当前在PriorityQueue执行诸如u.bound = bound(u);. 第一次通过循环，您设置 u.bound 并将其放入，下一次通过您再次更改 u.bound 而不先将其从队列中拉出。

如果您正在使用有组织的集合（HashSet/Map, TreeSet/Map,PriorityQueue等）并且您更改元素值以影响集合的组织方式，那么您将打破组织该集合的假设，并且它们将失败各种有趣的方式。我认为这就是这里正在发生的事情。

一些关于其他集合类型的问题：

于 2013-06-04T20:10:18.423 回答
0

另请注意，PriorityQueue (java 1.6) 似乎是尽最大努力排序。
我在使用 PriorityQueue 和 ConcurrentSkipListSet 的单元测试中发现了这一点，同时使用了相同的比较器。
PriorityQueue 尝试为新添加的项目找到正确的位置（它似乎遍历节点，但是一旦项目在所有先前的项目都较小之后变得更大，反之亦然，队列停止查找并将项目放在最后检查的旁边）。
与数组上的二进制搜索算法相比，它看起来好像搜索期间的上限和下限正在接近正确的位置，但仍然存在差距。当我使用具有相同比较器的 ConcurrentSkipListSet 重复相同的测试时，该集合实际上已正确排序！

于 2014-06-11T10:43:38.097 回答