普林斯顿大学算法课程二叉堆程序中可比较接口（Java）的实现

Question

我没有广泛使用 Java 进行编程，因此只了解该语言的基本知识。我在做 an algorithm course on coursera.

本课程给出的二叉堆程序是：

public class MaxPQ<Key extends Comparable<Key>>
{
    private Key[] pq;
    private int N;


    public MaxPQ(int capacity)
    { pq = (Key[]) new Comparable(capacity + 1);
    }
    public boolean isEmpty()
    { return N==0;}
    public void insert(Key key)
    { pq[++N] = x;
      swim(N);}
    private void swim(int k)
    {  while(k>1 && less(k/2,k))
       {
            exch(k,k/2);
            k=k/2;
       }
    }
    public key delMax()
    {
         Key max = pq[1];
         exch(1,N--);
         sink(1);
         pq[N+1] = null; //To prevent loitering.
         return max;
    }
    private void sink(int k)
    {
         while(2*k<=N){
            int j= 2*k;
            if(j<N && less(j,j+1))j++;
            if(!less(k,j)) break;
            exch(k,j);
            k=j;}
    }
    private boolean less(int i, int j)
    { return pq[i].compareTo(pq[j])>0; }
    private void exch(int i, int j)
    { Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }

compareTo() 方法将在 Key class 的定义中定义，当它覆盖可比较接口中的默认方法 compareTo 时。

现在，我了解到 comparable 是 java.lang 中的一个内置接口。在定义 MaxPQ class 时，使用的泛型类型是：

public class MaxPQ < Key extends Comparable < Key > >

由于 Comparable 是一个接口，而 Key 扩展了该接口，这意味着 key 也必须是一个接口。

现在我不明白这是怎么回事。

有人可以向我解释一下如果接口充当泛型类型会有什么好处，以及为什么 Key 需要扩展 Comparable<Key>。

如果您还可以给我一个示例，说明如何定义 Key（使用 Comparable 接口），那将非常有帮助。

Answer 1

Key extends Comparable < Key > 仅表示 Key 实现了接口 Comparable < Key >。仅此而已。

Answer 2

你缺的是理解

<Key extends Comparable<Key>>

这并不意味着 Key 是接口...这意味着 Key 是 Comparable 的子class，可以这样对待。

Comparable<Key> c = new Key();

最后，无论 Key 实现了一个 Comparable 接口，还是扩展了一个 class Comparable，都没有关系，因为在这两种情况下，它都可以充当 Comparable - 并且具有 Comparable 具有的方法。

普林斯顿大学算法课程二叉堆程序中可比较接口（Java）的实现

Implementation of comparable interface(Java) in Binary heaps program in algorithms course by Princeton Univeristy

java

algorithm

interface

comparable

binary-heap