Priorityqueue Java 的比较器无法正常工作

Question

我正在向 PriorityQueue 添加边，但由于某种原因，它们没有按它们的值进行排序，导致以后出现错误结果。

我的边缘类看起来像这样

class Edge implements Comparable<Edge>{
int value;
String dest;
String start;

public Edge(String start, String dest, int g) {
    this.dest = dest;
    value = g;
    this.start = start;
}
@Override
public int compareTo(Edge o) {
    int temp = value - o.value;
    if (temp > 0) {
        return 1;
    }
    if (temp < 0) {
        return -1;
    }
    return 0;
}

然而，当我运行我的代码，在属于节点“Springfield，MO”的 LinkedList 上执行 addAll 到 PriorityQueue 时，边缘按错误的顺序排序，如下所示，有什么问题？

queue.addAll(list.get(node));

我试图为 Edge 制作一个特定的比较器类并将其用作 PriorityQueue 中的参数，但我仍然得到相同的结果。

Answer 1

的内部结构PriorityQueue不是有序的，是堆，可以查这个问题。

当您使用peek或方法检索数据时poll，保证它是有序的。

但是在迭代队列时要小心：

方法 iterator() 中提供的 Iterator不保证以任何特定顺序遍历优先级队列的元素。如果您需要有序遍历，请考虑使用 Arrays.sort(pq.toArray())。