Приоритет приоритета Java не сортируется должным образом

Question

Я пытаюсь реализовать приоритетную очередь моего типа BBNode типа, но, похоже, он не рассеивает новые узлы так, как я ожидаю. Вместо того, чтобы иметь наименьший из них во главе очереди (как это работает сейчас), я хочу, чтобы наибольшее было там, но я не могу понять, как это сделать. Вот мой класс BBNode.

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 в методе сравнения, и я также попытался реализовать компаратор, но с теми же результатами.

Любая помощь приветствуется :)

Answer 1

Что, вероятно, происходит то, что вы изменяете bound экземпляров, которые в настоящее время находятся в PriorityQueue, когда вы делаете такие вещи, как u.bound = bound(u);. Первый раз через цикл вы устанавливаете u.bound и помещаете его в следующий раз, после чего вы снова меняете u.bound, не вытаскивая его из очереди в первую очередь.

Если вы используете организованную коллекцию (HashSet/Map, TreeSet/Map, PriorityQueue и т.д.) и изменить значение элементов таким образом, чтобы повлиять, как организована коллекция, вы нарушаете предположения, на которых, что коллекция организованных, и они потерпят неудачу различными интересными способами. Я думаю, это то, что здесь происходит.

Некоторые вопросы, которые говорят об этом для других типов коллекций:

• Immutable object as key in hash collections
• Should custom key objects be immutable ?If yes , then why?

Answer 2

Также отметим, что PriorityQueue (Java 1.6), как представляется, сортировать все усилия.
Я нашел это в модульном тесте, используя либо PriorityQueue, и ConcurrentSkipListSet, используя тот же Comparator.
Где PriorityQueue пытается найти нужное место для вновь добавленного элемента (он, кажется, перемещается по узлам, но как только элемент больше после того, как все предыдущие элементы были меньше, и наоборот, очередь перестает искать и помещает элемент рядом с последний проверен).
По сравнению с алгоритмом бинарного поиска в массиве, похоже, что верхняя и нижняя границы во время поиска закрываются вправо, но разрыв остается. Когда я повторяю тот же тест с помощью ConcurrentSkipListSet с тем же компаратором, набор действительно сортируется правильно!