Очередь приоритетов Java не сортируется должным образом

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

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

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


person Bhargav B    schedule 04.06.2013    source источник
comment
Ваш BNNode правильный, и вставка их в очередь с приоритетом работает просто отлично (наибольшая граница будет первой). Так почему вы считаете, что это неправильно? Какую пару значений, которые вы вставляете, в конечном итоге не вставляются должным образом?   -  person greedybuddha    schedule 04.06.2013
comment
Можете ли вы добавить раздел кода, где вы установили «u»?   -  person sharakan    schedule 05.06.2013
comment
В приведенном коде вы не назначаете u для указания на другой объект на каждой итерации, а просто меняете поля в ссылках на объект u. Если это так в вашем реальном коде, то всегда добавляется только один объект, и его значение изменяется в зависимости от последней версии v.   -  person Patricia Shanahan    schedule 05.06.2013


Ответы (2)


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

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

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

person sharakan    schedule 04.06.2013
comment
Это было именно так. Как только я создавал каждый новый объект перед тем, как вставить PQ, он работал! Забавно то, что эта логика указателя вызвала у меня проблемы в программе на C++ около месяца назад, но мне это не приходило в голову, что это может быть проблемой снова :( - person Bhargav B; 05.06.2013

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

person user3488500    schedule 11.06.2014