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
– Aniket Thakur

2013-08-21 11:42:15 +00:00
Commented Aug 21, 2013 at 11:42 — Aniket Thakur
– Aniket Thakur, Commented Aug 21, 2013 at 11:42

Katona · Accepted Answer · 2013-08-21 11:30:31Z

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, 2013 at 11:30

answered Aug 21, 2013 at 11:16

Katona

4,9011 gold badge25 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Katona Over a year ago

@JBNizet I am not sure, the original was Double.compare(d, time);, so I didn't change that

JB Nizet Over a year ago

But it doesn't make any sense.

committedandroider Over a year ago

Can you guys take a look at my use of a PriorityQueue in this question? stackoverflow.com/questions/28800287/…

JB Nizet · Accepted Answer · 2013-08-21 11:26:45Z

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, 2013 at 11:26

answered Aug 21, 2013 at 11:17

JB Nizet

694k94 gold badges1.3k silver badges1.3k bronze badges

2 Comments

Katona Over a year ago

by the way, PriorityQueue is possibly another example of sacrificing type safety for flexibility: if it had been declared as class PriorityQueue<E extends Comparable<E>>, then this error would have been caught at compile time, but then only elements with natural ordering could be put into the queue

yshavit Over a year ago

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

sanbhat · Accepted Answer · 2013-08-21 11:21:05Z

2

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

edited Aug 21, 2013 at 11:21

answered Aug 21, 2013 at 11:17

sanbhat

17.6k6 gold badges52 silver badges65 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 11:54:39Z

-1

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}

edited May 23, 2017 at 11:54

CommunityBot

11 silver badge

answered Aug 21, 2013 at 11:37

Aniket Thakur

69.4k43 gold badges290 silver badges299 bronze badges

1 Comment

committedandroider Over a year ago

Can you take a look at my use of a PriorityQueue in this question? stackoverflow.com/questions/28800287/…

Collectives™ on Stack Overflow

Java priority queues and comparable interface

4 Answers 4

3 Comments

2 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related