Why can't I add on PriorityQueue?

Question

I'm having troubles adding an Object Node to my PriorityQueue and I cant figure out why. When I add Node a, it has no problem.

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

q.add(a);

but if I add a second Node, it throws an exception saying "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);

My Node class is below:

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;
    }
}

I guess I'm just confused why it can add Node a but not add Node b. I looked up what ClassCastException is and I dont really see that I did that kind of exception since I'm adding a type Node to a PriorityQueue of type Nodes. I would appreciate any help. Thank you!

Your class doesn't implement `Comparable` which is a requirement for using `PriorityQueue`. — David Conrad, May 06 '20 at 17:11
This is why you should always add `@Override` when you intend to override. Then javac can prevent such mistakes. — Zabuzard, May 06 '20 at 17:28
I wonder why `PriorityQueue` is not implemented as `PriorityQueue>`? Why wait around for an exception to be thrown at run time? — WJS, May 06 '20 at 17:35
It existed before generics (Java 5), didnt it? So it would break backwards support. Same issue with other classes and methods in Java. — Zabuzard, May 06 '20 at 17:35
@WJS: One reason is that PriorityQueue lets you specify a custom ordering (using Comparator), so instances of `PriorityQueue` can be totally fine. In Java, a constructor can't impose constraints on the class's type arguments, so this means that `new PriorityQueue()` (without a custom ordering) can't be prevented even though it creates a broken instance. (If PriorityQueue had been added after Java 5, it might have avoided this problem by always requiring an explicit ordering. But, too late now.) — ruakh, May 06 '20 at 20:40
@ruakh Many classes allow you to specify a custom ordering. Seems to me since PriorityQueue was added during 1.5 at the same time with generics, the Comparable requirement could have been included. But I agree it is too late now. — WJS, May 06 '20 at 20:46
@WJS: Re: "PriorityQueue was added during 1.5": Whoops, good call. I was trusting Zabuzard's statement that it predated Java 5. I should have checked for myself. :-) In that case, a better answer is probably that they took the same approach as TreeSet, TreeMap, etc., which *do* predate Java 5. If they were writing it today, with more experience with generics -- and with the convenient `Comparator.naturalOrder()` -- they might do it differently. — ruakh, May 06 '20 at 20:50
@WJS: Actually, wait a sec, what you're saying doesn't make sense. Surely you mean that since PriorityQueue was added during 1.5, it could have required `Comparator`? Requiring `Comparable` would be needlessly restrictive. — ruakh, May 06 '20 at 20:53
@ruakh Perhaps I don't fully understand the use for `PriortyQueue`. My only thought was that there was a mechanism with the advent of generics to prevent a runtime class cast exception since it apparently needs to know how to prioritize items. I guess I'll have to research some more. — WJS, May 06 '20 at 20:59

score 5 · Accepted Answer · answered May 06 '20 at 17:11

The first one worked because it's the only one. From the second it needs to compare it against the first one to know where to place it on the priority queue. You need to implement the interface Comparable on your Node class and implement the compare (a, b) method. Then the Priority queue will know how to properly order the items.

score 1 · Answer 2 · edited May 06 '20 at 17:34

1

Node should inherit Comparable as follows:

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

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

edited May 06 '20 at 17:34

Zabuzard

25,064
8
58
82

answered May 06 '20 at 17:11

Sync it

1,180
2
11
29

Tom · Answer 3 · 2020-05-06T17:30:23.053

implements Comparable<Node> is missing in your 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;
    }
}

score 1 · Answer 4 · answered May 06 '20 at 17:22

Either Node must implement Comparable (as some answers suggest), or a Comparator must be provided when creating the PriorityQueue - according 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).

score 1 · Answer 5 · answered May 06 '20 at 17:28

From the documentation of 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]

The documentation of PriorityQueue#add(E) states it can throw:

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

And you create your PriorityQueue using the no-argument constructor, whose documentation states:

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

For an object to have a natural ordering it must implement the Comparable interface. Since your Node class does not implement Comparable you get a ClassCastException when adding the second element (due to there now being enough elements to start comparing them). There are at least two solutions:

Have Node implement 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...
    }
}

Pass a Comparator implementation when creating the PriorityQueue:

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

Also see Java : Comparable vs Comparator [duplicate].

Why can't I add on PriorityQueue?

5 Answers5