0 
fringe = new PriorityQueue<Node>(10,new Comparator<Node>(){
            @Override
            public int compare(Node node1,Node node2)
            {
                if (f(node1)>f(node2))
                    return 1;
                else
                    return -1;
            }
        });

我声明了一个 PQ 来存储一些节点，我想根据 f 值以非递减顺序存储节点。函数 f(Node node) 是计算节点的 f 值。所以我覆盖了比较器，但现在我发现一些具有较大 f 值的节点被放置在队列中具有较小 f 值的节点之前，我检查了所有但仍然找不到问题所在，我假设它可能是 PQ 声明的问题。任何人都可以帮助我吗？提前致谢！

4

3 回答 3

6

见这里。我引用：

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

所有可以保证的是，根据比较器，顶部元素是最小的元素。

于 2012-04-11T06:55:00.167 回答
1

正如@izomorphius 所说，PriorityQueue 不保证完全排序，只是头部总是最小的。

如果您想要完整订单 - 您可能想要选择以下可能性之一：

  1. 使用TreeSet- 但请注意它不允许重复。equals()此外，正如@JoonasPulakka 所述，您可能还想在这里覆盖hashCode()。
  2. 使用 a List- 填充它[无序]，然后使用Collections.sort(List,Comparator)根据您的比较器对其进行排序
  3. 使用一个数组 [ Node[]]，填充它 [unordered]，然后使用Arrays.sort()它根据您的比较器对其进行排序。

编辑：
您编辑的 Comparator 不强制执行完整排序，因此使用它的结果是未定义的：
let a, bbe two Nodes 这样f(a) == f(b)

compare(a,b) == compare(b,a) == -1

但是javadocs指出：

实现者必须确保所有 x 和 y 的 sgn(compare(x, y)) == -sgn(compare(y, x))。

因此，使用这个 [已编辑] 比较器的结果是未定义的。

EDIT2：
您的评论表明您正在寻找第二个标准 - “增加时间”。您可以将另一个字段添加long timestamp到您的Node对象，并在您Comparator返回基于此字段的结果当且仅当f(node1) == f(node2). 这将保证一致性，并实现所需的功能。

注意：当您第一次将元素添加到队列中[或创建对象时，如果它是一个选项]，此字段将被初始化一次[并且只有一次！]。

于 2012-04-11T07:00:59.313 回答
0

你也覆盖了equals()吗？正如Comparator docs中指出的那样，

当使用能够施加与等于不一致的排序的比较器来对排序集（或排序映射）进行排序时，应谨慎行事。假设带有显式比较器 c 的有序集合（或有序映射）与从集合 S 中提取的元素（或键）一起使用。如果 c 对 S 施加的排序与 equals 不一致，则有序集合（或有序映射）将表现得“奇怪”。特别是有序集合（或有序映射）将违反集合（或映射）的一般合同，它是根据等式定义的。

另请注意，当您覆盖时equals()，您还必须覆盖，正如Object docshashCode()中所指出的那样。

即使PriorityQueue不是（排序的）集合，如评论中所指出的那样，如果您想切换可以按特定顺序迭代的数据结构（队列不能，排序集可以），那么最好有compare(),equals()和hashCode()完全按照建议实施。

于 2012-04-11T06:53:55.003 回答