java - 将指定的比较器添加到java priorityqueue

Question

我很难理解 priorityqueue 如何使用 compareTo 方法对其内容进行排序。

我在上一门名为 Node.js 的类(class)。它有 4 个字段。

private char character;
private int frequency;
private Node left_child;
private Node right_child;

然后在我的另一个名为 Huffmantree 的类(class)中​​，我有一个优先级队列。

我的问题:

我想将对象节点放入队列中，以便在出队时它取决于节点的 (int) 频率。

现在我的 Node 类看起来像这样:

/**
 * Class for creating nodes with a specified character, frequency, 
 *  left- and right child.
 * implements comparable to be able to compare 2 nodes based on their 
 *  frequency.
*/
public class Node implements Comparable<Node>{

    private char character;
    private int frequency;
    private Node left_child;
    private Node right_child;

    public Node(char character, int frequency, Node left_child, Node 
                 right_child){

         this.character = character;
         this.frequency = frequency;
         this.left_child = left_child;
         this.right_child = right_child;
    }
    //Checks if two nodes have equal frequency.
    private boolean equals(Node n){

        return this.frequency == n.frequency;
    }



    @Override
    public int compareTo(Node other) {

        if(this.equals(other)){
            return 0;
        }else if(this.frequency > other.frequency){
            return 1;
        }else return -1;

    }

    //Print out current node
    @Override
    public String toString(){

        return "[" +this.character+"," + this.frequency +"]";

    }

这里我尝试实现 Comparable 接口(interface)我定义了一个 CompareTo 方法，将节点与其频率值进行比较。

在我的 HuffmanTree 类中，我尝试制作这样的优先级队列:

PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>()

但我不知道你会不会这样做。我卡住了，我还没有找到一个很好的例子。

Answer 1

由于您的 Node类已经实现了 Comparable接口(interface)，无需定义 Comparator<Node>并将其传递给您的队列对象，只需使用无参数构造函数:

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

据官方documentation :

public PriorityQueue() 

Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.

在这种情况下，您通过实现 compareTo 定义了一个自然顺序 Node 的方法对象，所以你已经完成了。另一个采用比较器的构造函数只能在队列中的元素不是 Comparable 时使用。 s，或者您希望使用不同的顺序:

// This queue will hand out nodes in the inverse order of their frequency
PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
    @Override
    public int compare(Node a, Node b) {
        return -a.compareTo(b);
    }
});