java优先级队列、自定义类和可比较的接口

Question

我有以下课程

private static class Node {
    public int id; // 0 indexed
    public int distFromS;

    Node(int id, int distFromS) {
        this.id = id;
        this.distFromS = distFromS;
    }
}

我正在将Node的实例存储在PriorityQueue中并对其进行操作

PriorityQueue<Node> procQueue = new PriorityQueue<Node>();
int[] distsFromS = new int[n];
Arrays.fill(distsFromS, -1);
// Read in s, add to processing queue
int s = (in.nextInt()) - 1; // 0 indexed
procQueue.add(new Node(s, 0));
// While queue isn't empty
while (procQueue.size() > 0) {
    // deque "curr". If we haven't already reached curr from s
    Node curr = procQueue.remove();
    if (distsFromS[curr.id] == -1) {
        // record distance.
        distsFromS[curr.id] = curr.distFromS;
        // enqueue all children of curr. distFromS = curr.distFromS + 6                    
        Iterator<Integer> itr = edges[curr.id].iterator();
        while(itr.hasNext()) {
            procQueue.add(new Node(itr.next(), curr.distFromS + EDGE_WEIGHT)); // ***Exception is here***
        }              
    }              
}    

但我得到了以下例外：

Exception in thread "main" java.lang.ClassCastException: Solution$Node cannot be cast to java.lang.Comparable
    at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:652)
    at java.util.PriorityQueue.siftUp(PriorityQueue.java:647)
    at java.util.PriorityQueue.offer(PriorityQueue.java:344)
    at java.util.PriorityQueue.add(PriorityQueue.java:321)
    at Solution.main(Solution.java:52)

我需要为Node实现compareTo吗？为什么？据我所知，我没有做任何比较

Answer 1

是的，您需要实现可比性

https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#add(E)

投掷

ClassCastException - if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering

Answer 2

From the docs:

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

您需要指定一个比较器，或者您的类需要具有可比性
否则PriorityQueue无法知道哪些对象具有优先级

Answer 3

您需要使类节点实现可比性

private static class Node implements Comparable<Node> {

    public int id; // 0 indexed
    public int distFromS;

    Node(int id, int distFromS) {
        this.id = id;
        this.distFromS = distFromS;
    }

    @Override
    public int compareTo(Node another) {
        // your codes here
    }
}

或者在构造优先级队列时给出一个比较器

PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
    @Override
    public int compare(Node o1, Node o2) {
        // your codes here
    }
});