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

h22fl7wq  于 2021-07-12  发布在  Java
关注(0)|答案(2)|浏览(397)

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

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] 我希望优先级队列中的元素先按级别排序,然后按数据排序。

sbtkgmzw

sbtkgmzw1#

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

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

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

2exbekwf

2exbekwf2#

方法tostring不能按检索顺序显示元素。所以,这并不意味着你的比较器是错误的。
以下是用javadoc为priorityqueu编写的(重点是我的):
这个类及其迭代器实现了集合和迭代器接口的所有可选方法。方法iterator()中提供的迭代器和方法spliterator()中提供的spliterator不能保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历,请考虑使用arrays.sort(pq.toarray())。
这里没有显式地编写它,但是tostring依赖于迭代器,因此元素也可能不会显示在预期的或其他元素中。tostring方法是在类集合中定义的,在这里没有被具体重写。
priorityqueu可能是使用数组中的二进制堆实现的。从这里开始,自然地,迭代是按数组顺序进行的。以正确的顺序显示元素需要将它们从队列中删除,因此除非将副本排序到其他地方,否则这是不可能的,因为对于简单的tostring来说,副本太重了。

相关问题