为什么我不能添加 PriorityQueue？

Question

我在将对象节点添加到我的 PriorityQueue 时遇到问题，我无法弄清楚原因。当我添加节点a时，它没有问题。

PriorityQueue<Node> q = new PriorityQueue<Node>();
Node a = new Node('a', 1);

q.add(a);

但是如果我添加第二个节点，它会抛出异常 "java.lang.ClassCastException: Node cannot be cast to java.lang.Comparable"

PriorityQueue<Node> q = new PriorityQueue<Node>();
Node a = new Node('a', 1);
Node b = new Node('b', 2);

q.add(a);
q.add(b);

我的节点class如下：

public class Node {
    public int count;
    public char character;
    public Node left;
    public Node right;

    public Node(char character, int count) {
        this(character, count, null, null);
    }

    public Node(char character, int count, Node left, Node right) {
        this.count = count;
        this.character = character;
        this.left = left;
        this.right = right;
    }

    public int compareTo(Node other) {
        return this.count - other.count;
    }
}

我想我只是很困惑为什么它可以添加节点 a 但不能添加节点 b。我查了一下 ClassCastException 是什么，但我并没有真正看到我做了那种异常，因为我正在将一个类型 Node 添加到一个类型为 Nodes 的 PriorityQueue。我将不胜感激任何帮助。谢谢！

Answer 1

Node 应该继承 Comparable 如下：

public class Node implements Comparable<Node> {
    ...

    @Override
    public int compareTo(Node n) {
        ...
    }
}

Answer 2

第一个有效，因为它是唯一的。从第二个开始，它需要将它与第一个进行比较，以了解将其放置在优先级队列中的哪个位置。你需要在你的Nodeclass上实现Comparable接口，实现compare(a,b)方法。然后优先级队列将知道如何正确排序项目。

Answer 3

implements Comparable<Node> 在您的 class Node 中缺失：

public class Node implements Comparable<Node> {
    public int count;
    public char character;
    public Node left;
    public Node right;

    public Node(char character, int count) {
        this(character, count, null, null);
    }

    public Node(char character, int count, Node left, Node right) {
        this.count = count;
        this.character = character;
        this.left = left;
        this.right = right;
    }

    @Override
    public int compareTo(Node other) {
        return this.count - other.count;
    }
}

Answer 4

要么 Node 必须实现 Comparable（如某些答案所建议的那样），要么或创建 [=] 时必须提供 Comparator 13=] - 根据 javadoc

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

Answer 5

来自 PriorityQueue 的文档：

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). [emphasis added]

PriorityQueue#add(E) 的文档说明它可以抛出：

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

然后您使用 no-argument constructor 创建 PriorityQueue，其文档说明：

Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.

要使对象具有自然顺序，它必须实现 Comparable 接口。因为你的 Node class 没有实现 Comparable 你在添加第二个元素时得到 ClassCastException （因为现在有足够的元素开始比较它们）。至少有两种解决方案：

有Node实施Comparable<Node>:

public class Node implements Comparable<Node> {

    // fields and other methods omitted for brevity

    @Override // annotation forces compiler to check if method actually overrides anything
    public int compareTo(Node other) {
        // compare 'this' and 'other' based on their properties and return result...
    }
}

创建 PriorityQueue 时传递 Comparator 实现：

PriorityQueue<Node> queue = new PriorityQueue<>((left, right) -> /* compare */);

另见 Java : Comparable vs Comparator [duplicate]。

为什么我不能添加 PriorityQueue？

Why can't I add on PriorityQueue?

java

priority-queue

nodes