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

Question

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

我的优势class是这样的

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 制作一个特定的比较器 class 并将其用作 PriorityQueue 中的参数，但我仍然得到相同的结果。

Answer 1

PriorityQueue的内部结构是无序的，是一个堆，可以查看的问题。

当您使用方法 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()).

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

Comparator not working correctly for Priorityqueue Java

java

linked-list

priority-queue

comparator