PriorityQueues、自定义类和 Comparable 接口

Question

我有以下class。

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

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).

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

Answer 2

是的，你需要实现可比性。

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 3

您需要使您的 class 节点实现具有可比性

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时给一个Comparator

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

PriorityQueues、自定义类和 Comparable 接口

PriorityQueues, custom classes, and the Comparable interface

java

priority-queue

comparable

PriorityQueues、自定义 类 和 Comparable 接口

PriorityQueues, custom classes, and the Comparable interface

java

priority-queue

comparable

PriorityQueues、自定义类和 Comparable 接口