Java优先队列和可比接口

Question

Java优先队列和可比接口

8

我刚学习了优先队列并尝试使用可比较的接口测试它的行为。

代码片段：

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

代码可以编译，但在主线程中抛出异常：java.lang.ClassCastException: kinga 无法转换为 java.lang.Double。

这里出了什么问题？有人能告诉我可比较性和优先队列是如何工作的吗？

- JohnnyHunter

请看我的回答，其中包含了相应的修改后的代码和输出。 - Aniket Thakur

4个回答

8

class kinga implements Comparable<Double>

这不太合理。虽然你的类可以与Double进行比较，但Double却不知道这一点，因此不能与kinga实例进行良好的比较，这将破坏Comparable接口的契约。而且由于kinga无法与另一个kinga进行比较，因此您无法使用PriorityQueue<kinga>。

应该改为

class Kinga implements Comparable<Kinga>

请注意大写字母，以尊重Java命名规范，意思是：Kinga实例可以相互比较。

compareTo方法应该

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

这句话的意思是：如果我的 d 比另一个 Kinga 的 d 大，那么我比他更强大。

- JB Nizet

顺便说一下，PriorityQueue 可能是为了灵活性而牺牲类型安全的另一个例子：如果它被声明为 class PriorityQueue<E extends Comparable<E>>，那么这个错误将在编译时被捕获，但只有具有自然排序的元素才能放入队列中。 - Katona

2

为了更好地理解，考虑 Kinga k; Double d;。在这种情况下，k.compareTo(d); 可以正常工作，但是 d.compareTo(k) 呢？优先队列有时会调用后者，这就是导致异常的原因。 - yshavit

2

PriorityQueue<kinga> 会在 add 方法中期望得到实现了 Comparable<kinga> 接口的对象。如果传入一个实现了 Comparable<Double> 接口的对象，会抛出 ClassCastException 异常。

- sanbhat

-1

Can somebody tell me how comparable and priority queues work?

首先要了解 Comparable 和 Comparator 接口之间的区别。

现在回答你的问题，你可以像下面这样做：

首先为 Kinga 创建一个比较器（Comparator）。

class comparableKinga implements Comparator<kinga> {

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

然后在构造函数中使用这个比较器创建你的优先队列

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

输出与预期相符

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

- Aniket Thakur

你能否看一下我在这个问题中使用PriorityQueue的方式？http://stackoverflow.com/questions/28800287/how-to-restore-the-priorityqueue-to-its-initial-state-before-the-method-call?noredirect=1#comment45875800_28800287 - committedandroider

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Katona · Accepted Answer

kinga应该与kinga进行比较，而不是Double，所以：

class kinga implements Comparable<kinga>

这意味着你的compareTo方法必须更改为以下内容：

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