Java 实现 PriorityQueue - 当没有提供 Comparator 时

Question

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

Object[] qArray = new Object[initial_Size];

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

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

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

但是，当用户不提供默认比较器时就会出现问题。我可能处理这个问题的一种方法是让我的 PriorityQueue 类实现 Comparator 并让比较器执行以下比较 -

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

但是，这个比较器有点蹩脚。它显然对 String 类型的 PriorityQueues 非常有效，但在(比方说)整数的情况下，就不完全是(它会认为 5 大于 49)。另一种方法是强制用户提供比较器——但我知道 Java Util 的 PriorityQueue 实现要好得多。

因此，我尝试对 Java 的 PriorityQueue 进行一点逆向工程，并在不传递比较器的情况下初始化自定义类类型的优先级队列。

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

所以这个 siftUpComparable 方法可能包含一些关于 util 包如何进行比较的重要线索，但是当我试图阅读源代码时，我迷路了。

所以这里的任何实现想法 - 如果在提供的对象类型(如 Integer 或 String)上定义了自然排序比较器，则默认情况下应使用它。

Answer 1

Exception 揭示了一切:如果您不提供 Comparator，Java 会尝试将给定对象转换为 Comparable。

您不能只将任意类型的对象与通用算法进行比较。这正是您必须提供 Comparator 或确保您的对象支持 compareTo 方法并实现 Comparable 的原因。