heap - Java PriorityQueue 实现 : Why Object[] queue instead of E[] queue? siftUp/siftDownComparable 中 "key"的用途是什么？

Question

我正在研究 JDK implementation of PriorityQueue .

1)整个队列存放在

 transient Object[] queue;

为什么不使用泛型 E 声明数组？ (相反，有很多将 E 强制转换为类中的对象。)

2) siftUpComparable/siftDownComparable 方法的第一行是

    Comparable<? super E> key = (Comparable<? super E>)x;

这是一个保护子句来验证 x 是可比较的吗？ (否则，为什么不直接使用 x 呢？)

这是整个方法:

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

Answer 1

1) 如果没有对对象类的引用，则无法实例化泛型数组。有关示例，请参见下面的 JavaDevil 评论。但是，通过创建一个对象数组，就不需要将类的实例提供给 PriorityQueue。

E[] array = new E[10]; // won't compile

2) PriorityQueue 可以通过 Comparable 的对象 compareTo() 对其元素进行排序方法或对不一定是 Comparable 的对象使用 Comparator。只有在创建 PriorityQueue 时未提供 Comparator 时，才会调用 siftDownComparable 方法。由于类型参数没有规定<E extends Comparable> ，你需要明确地转换它。这是 siftDown() 方法。

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}