java在自定义对象上使用优先级队列的更好方法

Question

我有一个类Node，它包含2个字段，我基于字段len为这个Node的对象构建了一个优先级队列

现在我有两种方法可以做到这一点：

1. PriorityQueue<Node> pq = new PriorityQueue<Node>(n);//size n queue
   此方法允许在类节点上实现可比较的接口，有点像这样：

   @Override  
   public int compareTo(Node o){  
       return this.len- o.len;
   }
   

2. 另一种方式是：

   PriorityQueue<Node> pq = new PriorityQueue<Node>(n, new Node());

   这允许使用比较器接口：

   @Override  
   public int compareTo(Node node1, Node node2){  
       return node1.len-node2.len;}
   

以下哪种方式更可取？使用其中一种方法是否有利/不利

Answer 1

在我看来，第二个有点虚假。需要一个比较器，你给它一个对象，它“碰巧实现”了一个比较器接口，作为（我想）它真正用途的副业。在这种使用中，节点实际上并不是节点，它只是一个带有方便比较器的东西

以下是我的看法：

1. 如果您的节点具有独立于但与此特定优先级队列使用所需的顺序相同的自然顺序，那么它们应该实现可比性，现在您可以在优先级队列中使用它

2. 否则，如果这个特定情况下只需要一个特定的顺序，那么将Comparator实现为一个完全独立于节点实现的类

Answer 2

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x, queue, comparator);
    else
        siftUpComparable(k, x, queue);
}

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (key.compareTo((T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = key;
}

private static <T> void siftUpUsingComparator(
    int k, T x, Object[] es, Comparator<? super T> cmp) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (cmp.compare(x, (T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = x;
}

对于第二个选项：您需要一个实现Comparator的NodeComparator，这样做之后，这两个是相同的。 在我看来，Comparator是一个比较对象的工具，Comparable表示对象的能力