Почему я не могу добавить PriorityQueue?

Question

У меня проблемы с добавлением узла объекта в мой PriorityQueue, и я не могу понять, почему. Когда я добавляю Node a, у него нет проблем.

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

q.add(a);

, но если я добавляю второй Node, он генерирует исключение: «java .lang.ClassCastException: Node не может быть преобразован в 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);

Мой класс Node ниже:

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 в PriorityQueue типа Nodes. Буду признателен за любую помощь. Спасибо!

Answer 1

Первый сработал, потому что он единственный. Со второго ему нужно сравнить его с первым, чтобы узнать, где разместить его в очереди приоритетов. Вам необходимо реализовать интерфейс Comparable в своем классе Node и реализовать метод compare (a, b). Тогда очередь Priority будет знать, как правильно заказывать товары.

Answer 2

Из документации PriorityQueue:

Неограниченный приоритет очередь на основе кучи приоритета. Элементы приоритетной очереди упорядочиваются в соответствии с их естественным порядком или Comparator, предоставляемым во время построения очереди, в зависимости от того, какой конструктор используется. Очередь с приоритетом не допускает элементов null. Очередь с приоритетом, основанная на естественном порядке, также не позволяет вставлять несопоставимые объекты (это может привести к ClassCastException). [ добавлено выделение ]

В документации PriorityQueue#add(E) указано, что он может выдавать:

ClassCastException - если указанный элемент не может быть сравнен с элементами, находящимися в данный момент в этой приоритетной очереди в соответствии с порядок приоритетной очереди

И вы создаете свой PriorityQueue, используя конструктор без аргументов , в документации которого указано:

Создает PriorityQueue с начальной емкостью по умолчанию (11), которая упорядочивает элементы в соответствии с их естественным порядком .

Чтобы объект имел естественный порядок, он должен реализовывать Comparable интерфейс. Поскольку ваш класс Node не реализует Comparable, вы получаете ClassCastException при добавлении второго элемента (из-за того, что теперь достаточно элементов, чтобы начать их сравнивать). Существует как минимум два решения:

1. Есть 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...
       }
   }
   

2. Передать реализацию Comparator, когда создание PriorityQueue:

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

Также см. Java: Comparable vs Comparator [дубликат] .

Answer 3

Либо Node должен реализовывать Comparable (как предлагают некоторые ответы), или a Comparator должен быть предоставлен при создании PriorityQueue - в соответствии с javado c

Неограниченная очередь приоритетов, основанная на куче приоритетов. Элементы очереди с приоритетом упорядочиваются в соответствии с их естественным порядком или с помощью Comparator, предоставляемого во время создания очереди, в зависимости от того, какой конструктор используется. Очередь с приоритетом не допускает пустых элементов. Очередь с приоритетом, основанная на естественном порядке, также не позволяет вставлять несопоставимые объекты (при этом может получить ClassCastException).

Answer 4

implements Comparable<Node> отсутствует в вашем классе 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 5

Node должен наследовать Comparable следующим образом:

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

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