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() 对其元素进行排序方法或对不一定是可比较的对象使用比较器。仅当创建 PriorityQueue 时未提供 Comparator 时，才会调用 siftDownComparable 方法。由于类型参数没有规定<E extends Comparable> ，您需要显式地转换它。这是 siftDown() 方法。

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