我正在尝试使用带有自定义比较器的优先级队列,但无法实现预期的功能:
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]
我希望优先级队列中的元素先按级别排序,然后按数据排序。
2条答案
按热度按时间sbtkgmzw1#
实际上逻辑是正确的,唯一的事情是我正在尝试执行sysout,然后它以我插入的顺序显示,当我使用remove操作时,优先级队列数据以预期的格式出现。
输出:0:1 1:2 1:4 2:2 2:3 2:5 2:7
2exbekwf2#
方法tostring不能按检索顺序显示元素。所以,这并不意味着你的比较器是错误的。
以下是用javadoc为priorityqueu编写的(重点是我的):
这个类及其迭代器实现了集合和迭代器接口的所有可选方法。方法iterator()中提供的迭代器和方法spliterator()中提供的spliterator不能保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历,请考虑使用arrays.sort(pq.toarray())。
这里没有显式地编写它,但是tostring依赖于迭代器,因此元素也可能不会显示在预期的或其他元素中。tostring方法是在类集合中定义的,在这里没有被具体重写。
priorityqueu可能是使用数组中的二进制堆实现的。从这里开始,自然地,迭代是按数组顺序进行的。以正确的顺序显示元素需要将它们从队列中删除,因此除非将副本排序到其他地方,否则这是不可能的,因为对于简单的tostring来说,副本太重了。