我想實現我的類類型BBNode的優先級隊列,但它似乎沒有像我期望的那樣篩選新節點。我不想讓最小的人進入隊列的最前面(它現在是如何工作的),我希望最大的人在那裏,但我無法弄清楚如何做到這一點。這是我的BBNode類。Java優先級隊列沒有正確排序
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;
}
}
而這裏是我使用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);
}
}
}
對不起,在最後的格式糟透了。最後一個括號對應於while循環。
我也嘗試在比較方法中切換-1和1,並且我也試過實現一個比較器,但結果相同。
任何幫助表示讚賞:)
你的BBNode是正確的,並將它們插入到優先級隊列中工作得很好(最大的邊界是第一個)。那麼爲什麼你認爲它錯了?什麼是你插入的幾個值最終沒有被正確插入? – greedybuddha
你可以在你設置'u'的地方添加代碼段嗎? – sharakan
在引用的代碼中,您並未指定u指向每次迭代中的不同對象,只是更改對象u引用中的字段。如果實際代碼中出現這種情況,那麼只會添加一個對象,並且其值會根據最新的v而改變。 –