java - 比较器不能为 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的内部结构是无序的，是一个堆，可以查看this问题。

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

但是迭代队列时要小心:

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