Java priority queues and comparable interface

Question

I've just been learning about priority queues and thought I'd try how it behaves with comparable interface.

Code Snippet:

import java.util.PriorityQueue;

class kinga implements Comparable<Double> {
    double time=909.909;
    double d;

    public kinga(double a) {  
        this.d=a;
    }

    public int compareTo(Double d) {
        return Double.compare(d, time);
    }

    public static void main(String arg[]) {
        PriorityQueue<kinga> r=new PriorityQueue<kinga>();

        r.add( new kinga(4545.45));
        r.add( new kinga(45.4));
        r.add( new kinga(1235.45));

        System.out.println(r.poll()+" "+r.poll()+" "+r.poll());
    }
}

It compiles but gives me Exception in thread "main" java.lang.ClassCastException: kinga cannot be cast to java.lang.Double.

What is wrong here. Can somebody tell me how comparable and priority queues work?

see my answer for the edited code and output for the same. – Aniket Thakur Aug 21 '13 at 11:42 — Aniket Thakur, Aug 21 '13 at 11:42

Katona · Accepted Answer · 2013-08-21T11:30:31.717

11

kinga should be comparable with kinga, not Double, so:

class kinga implements Comparable<kinga>

which means your compareTo method has to be changed to this:

public int compareTo(kinga o) {
    return Double.compare(o.d, d);
}

edited Aug 21 '13 at 11:30

answered Aug 21 '13 at 11:16

Katona

4,816
23
27

@JBNizet I am not sure, the original was `Double.compare(d, time);`, so I didn't change that – Katona Aug 21 '13 at 11:24
But it doesn't make any sense. – JB Nizet Aug 21 '13 at 11:25
Can you guys take a look at my use of a PriorityQueue in this question? http://stackoverflow.com/questions/28800287/how-to-restore-the-priorityqueue-to-its-initial-state-before-the-method-call?noredirect=1#comment45875800_28800287 – committedandroider Mar 02 '15 at 00:43

JB Nizet · Answer 2 · 2013-08-21T11:26:45.827

8

class kinga implements Comparable<Double>

That doesn't make sense. Although your class will compare fine with Double, Double is unaware of that, and won't compare fine with instances of kinga, which will break the Comparable contract. And since a kinga can't compare with another kinga, you can't use a PriorityQueue<kinga>.

It should be

class Kinga implements Comparable<Kinga>

(note the upper-case, to respect the Java naming conventions), which means: Kinga instances are comparable together.

The compareTo method should be

@Override
public int compareTo(Kinga other) {
    return Double.compare(this.d, other.d);
}

which means: I'm bigger than another Kinga if my d is bigger than the other Kinga's d.

edited Aug 21 '13 at 11:26

answered Aug 21 '13 at 11:17

JB Nizet

678,734
91
1,224
1,255

by the way, `PriorityQueue` is possibly another example of sacrificing type safety for flexibility: if it had been declared as `class PriorityQueue>`, then this error would have been caught at compile time, but then only elements with natural ordering could be put into the queue – Katona Aug 21 '13 at 11:38
2

+1 To drive it home, consider `Kinga k; Double d;`. In this case,`k.compareTo(d);` works fine, but what about ’d.compareTo(k)`? The priority queue will call the latter sometimes, which is what causes the exception. – yshavit Aug 21 '13 at 12:06

sanbhat · Answer 3 · 2013-08-21T11:21:05.810

2

PriorityQueue<kinga> will expect Comparable<kinga> in the add method. Passing a Comparable<Dobule> instead, is throwing ClassCastException

edited Aug 21 '13 at 11:21

answered Aug 21 '13 at 11:17

sanbhat

17,522
6
48
64

score -1 · Answer 4 · edited May 23 '17 at 11:54

Can somebody tell me how comparable and priority queues work?

First get the difference between Comparable and Comparator interfaces.

Now for your question you can do something like below

First create a Comparator for Kinga

class comparableKinga implements Comparator<kinga> {

@Override
public int compare(kinga o1, kinga o2) {
    return Double.compare(o1.getD(),o2.getD());
}
}

Then create your priority queue with this Comparator in the constructor

class kinga {

double d;

public kinga(double a) {
    this.d = a;
}

public double getD() {
    return this.d;
}

@Override
public String toString() {
    return "kinga{" +
            "d=" + d +
            '}';
}

public static void main(String arg[]) {
    PriorityQueue<kinga> r = new PriorityQueue<kinga>(11,new comparableKinga());


    r.add(new kinga(4545.45));
    r.add(new kinga(45.4));
    r.add(new kinga(1235.45));

    System.out.println(r.poll() + " " + r.poll() + " " + r.poll());
}
}

Output is as expected

kinga{d=45.4} kinga{d=1235.45} kinga{d=4545.45}

Can you take a look at my use of a PriorityQueue in this question? http://stackoverflow.com/questions/28800287/how-to-restore-the-priorityqueue-to-its-initial-state-before-the-method-call?noredirect=1#comment45875800_28800287 — committedandroider, Mar 02 '15 at 00:43

Java priority queues and comparable interface

4 Answers4