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

Question

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

我在 class 上有一个名为 Node. 它有 4 个字段。

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

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

我的问题：

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

现在我的节点 class 看起来像这样：

/**
 * 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接口我定义了一个 CompareTo 方法，将节点与其频率值进行比较。

在我的 HuffmanTree class 中，我尝试创建一个这样的优先级队列：

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

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

Answer 1

compareTo() 用于比较两个对象。

所以如果你想根据频率进行比较，那么你应该写：

public int compareTo(Node other) {    
        if(frequency>other.frequency)
            return 1;
        else if(frequency==other.frequency) 
             return 0;
         return -1;
    }

此处我们将当前频率与参数化对象进行比较。

您可以从here

获取详细说明

你不需要这个：

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

你可以这样写：

PriorityQueue pq = new PriorityQueue<>();

Answer 2

由于您的 Node class 已经实现了 Comparable 接口，因此无需定义 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.

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

// 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);
    }
});

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

adding a specified comparator to java priorityqueue

java

priority-queue