java - TreeSet 排序不正确

Question

我需要保留一个排序的节点列表，从第一个开始，然后获取所有相邻节点。第一个节点和所有其他节点都带有一个种子值，用于根据最低种子值确定接下来将使用哪个节点，一旦一个节点被用于获取相邻节点，它就会被标记为已使用，因此它不会被扩展再次即使它有最低的种子。

我的问题是使用的值似乎爬到顶部并完全停止搜索，因为在 3 次迭代之后，顶部节点将成为一个不断扩展的使用节点。这是我的 TreeSet 代码以及数字逐渐增加的示例

private static TreeSet<Node> nodelist = new TreeSet<Node>(
        new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.totalVal > o2.totalVal) {
                    if (o2.isValid)
                        return +1;
                    else
                        return -1;
                } else if (o1.totalVal < o2.totalVal)
                    return -1;
                else
                    return 0;
            }
        });

这是每组插入之后 TreeSet 的迭代，第四次之后的所有内容都与第四次相同，因为没有新元素可以读取。

first set
true, 37.24913792078372
true, 38.12142238654117
true, 38.57602191449718
true, 38.57658845611187
true, 39.427369179869515
false, 36.6742416417845

second set
true, 37.84689665786984
false, 37.24913792078372
true, 38.12142238654117
true, 38.57602191449718
true, 38.57658845611187
true, 39.18376618407356
true, 39.427369179869515
false, 36.6742416417845

third set
true, 38.4682957019364
false, 37.84689665786984
false, 37.24913792078372
true, 38.12142238654117
true, 38.57602191449718
true, 38.57658845611187
true, 39.18376618407356
true, 39.427369179869515
true, 39.814763008775685
false, 36.6742416417845

fourth set
false, 38.4682957019364
false, 37.84689665786984
false, 37.24913792078372
true, 38.12142238654117
true, 38.57602191449718
true, 38.57658845611187
true, 38.590228543643214
true, 39.11409973215888
true, 39.18376618407356
true, 39.427369179869515
true, 39.814763008775685
true, 40.469726317012984
false, 36.6742416417845

到目前为止，我推断它与树结构有关，但无法真正理解为什么要这样做。我尝试过使用类似的方法来处理优先级队列和排序数组列表实现，两者都做了同样的事情，尽管在停止之前它们会再进行大约 2 次迭代。

有什么帮助吗？

Answer 1

契约(Contract)Comparator要求比较是稳定的——即如果 compare(a,b) < 0然后compare(b,a) > 0等等。看起来你没有那样做。我怀疑你应该测试 o1.isvalid以某种方式在您的 else block 中，但没有足够的代码可以确定。

你可能更喜欢这样的东西:

private static TreeSet<Node> nodelist = new TreeSet<Node>(
        new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if ( o1.isValid == o2.isValid ) {
                    // Both valid/invalid - it's the totals that control the order.
                    return o1.totalVal - o2.totalVal;
                } else {
                    // One valid, one not, move all invalids to one end.
                    return o1.isValid ? -1 : 1;
                }
            }
        });