Java实现PriorityQueue-当没有提供比较器时

Question

我正在尝试用Java实现我自己的通用PriorityQueue版本（使用二进制堆）。我已经选择使用对象数组作为我的堆。

Object[] qArray = new Object[initial_Size];

如果一个用户提供了一个比较器--这个实现非常简单，因为我可以在进行元素比较时使用比较器的compare方法。

Comparator<T> comparator; //Set to a user-provided comparator in my constructor.

if(comparator.compare((T)qArray[i], (T)qArray[j])
    //do something

然而，当用户没有提供默认比较器时，问题就来了。一种可能的方法是让PriorityQueue类实现比较器，并让比较器执行以下比较-

@Override
public int compare(T o1, T o2)
{
    if(this.comparator == null) //no comparator provided by user
    {
        return o1.toString().compareTo(o2.toString());
    }
    else
    {
        return this.comparator.compare(o1, o2);
    }
}

public class TestClass {

    public class SomeClass
    {
        int value;
        SomeClass(int value)
        {
            this.value = value;
        }
    }

    public static void main(String[] args)
    {
        TestClass tClass = new TestClass();
        TestClass.SomeClass sClass1 = tClass.new SomeClass(10);
        TestClass.SomeClass sClass2 = tClass.new SomeClass(20);

        PriorityQueue<TestClass.SomeClass> pQueue = new PriorityQueue<TestClass.SomeClass>();
        pQueue.add(sClass1);
    }
}

因此，这里的任何实现思路--其中，如果在提供的对象类型（如整数或字符串）上定义了自然排序比较器，则默认情况下应该使用该比较器。

Answer 1

这个异常揭示了一切：如果不提供comparator，Java会尝试将给定对象强制转换为comparabile。

不能只将任意类型的对象与泛型算法进行比较。这就是为什么您必须提供比较器或者确保您的对象支持compareTo方法并实现comparable。