Java 优先级队列中的自定义比较器

Question

我正在尝试使用带有自定义比较器的优先级队列，但是我无法实现预期的功能。:

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class TestMain {

    public static void main(String[] args) {
        Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
            public int compare(Node a, Node b) {
                if(a.level == b.level) {
                    return a.data - b.data;
                }
                return a.level - b.level;
            }
        });
        
        queue.add(new Node(0,1));
        queue.add(new Node(1,2));
        queue.add(new Node(1,4));
        queue.add(new Node(2,3));
        queue.add(new Node(2,7));
        queue.add(new Node(2,2));
        queue.add(new Node(2,5));
        
        System.out.println(queue);
    }
    
    private static class Node {
        int level;
        int data;
        
        Node(int level, int data) {
            this.level = level;
            this.data = data;
        }
        
        public String toString() {
            return level + ":" + data;
        }
    }
}

预期输出 = [0:1, 1:2, 1:4, 2:2, 2:3, 2:5, 2:7] 实际输出 = [0:1, 1:2, 1:4, 2:3, 2:7, 2:2, 2:5]

我希望优先级队列中的元素先按级别排序，然后按数据排序。

Answer 1

实际上逻辑是正确的，唯一的问题是我正在尝试执行 sysout，然后它按照我插入的顺序显示，当我对优先级队列使用删除操作时，数据以预期的格式出现。

while(!queue.isEmpty()) {
    System.out.println(queue.remove());
}

输出： 0:1 1:2 1:4 2:2 2:3 2:5 2:7

Answer 2

toString 方法可能无法按检索顺序显示元素。所以，这并不意味着你的比较器不正确。

下面写在javadoc for PriorityQueu（重点是我的）：

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() and the Spliterator provided in method spliterator() are not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

这里没有明确写明，但是toString依赖于迭代器，因此元素也可能不会以预期的方式显示。 toString 方法在 class 集合中定义，此处未具体覆盖。

PriorityQueu 可能是使用数组中的二进制堆实现的。从那里，很自然地可以得出迭代是按数组顺序进行的。以正确的顺序显示元素需要将它们从队列中移除，因此除了在其他地方排序副本之外是不可能的，这对于简单的 toString 来说太重了。

Java 优先级队列中的自定义比较器

Custom Comparator in Priority queue in Java

java

comparator