我正在尝试使用优先级队列来实现Dijkstra的算法来寻找最短路径.在算法的每个步骤中,我删除距离优先级队列最短距离的顶点,然后更新优先级队列中每个邻居的距离.现在我读到Java中的优先级队列在编辑其中的元素(确定排序的元素)时不会重新排序,所以我试图通过插入和删除虚拟顶点来强制它重新排序.但这似乎并没有起作用,而且我一直试图解决这个问题.
这是顶点对象和比较器的代码
class vertex {
int v, d;
public vertex(int num, int dis) {
v=num;
d=dis;
}
}
class VertexComparator implements Comparator {
public int compare (Object a, Object b) {
vertex v1 = (vertex)a;
vertex v2 = (vertex)b;
return v1.d-v2.d;
}
}
这是我运行算法的地方:
int[] distances=new int[p];
Comparator<vertex> comparator = new VertexComparator();
PriorityQueue<vertex> queue = new PriorityQueue<vertex>(p, comparator);
for(int i=0; i<p; i++) {
if(i!=v) {
distances[i]=MAX;
}
else {
distances[i]=0;
}
queue.add(new vertex(i, distances[i]));
}
// run dijkstra
for(int i=0; …这直接来自Java Docs:
该类及其迭代器实现了Collection和Iterator接口的所有可选方法.方法iterator()中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素.如果需要有序遍历,请考虑使用Arrays.sort(pq.toArray()).
基本上,我的PriorityQueue工作正常,但是使用自己内置的toString()方法将其打印到屏幕上会让我看到这个异常现象,并且想知道是否有人可以解释为什么它是迭代器提供的(并且使用过)内部)不按自然顺序遍历PriorityQueue？
我有一个涉及迭代优先级队列的java赋值.队列由带有字符串和int的对象组成,我需要有一种方法来检查队列中所有对象的单独对象的字符串.
这是一个迭代器对象的最佳方法吗？这看起来太乱了.我可以出列队并入队,但这似乎效率低下.也许是一个foreach循环？
简短的故事,我正在实现一个图表,现在我正在研究Kruskal,我需要一个优先级队列.我对优先级队列的定义是具有最小密钥的元素将首先出现？这是错的吗？因为当我在队列中插入加权边(或数字)时,它们不会最终排序.
PriorityQueue<Integer> tja = new PriorityQueue<Integer>();
tja.add(55);
tja.add(99);
tja.add(1);
tja.add(102);
tja.add(54);
tja.add(51);
System.out.println(tja);
那将打印出来; [1,54,51,102,99,55].这不像我希望的那样排序!是的,我创建了一个进入优先级队列的comperator,该队列从edge对象中提取数字并根据该int进行比较.所以这应该有用,或者我只是完全误解了这个数据结构如何工作的整个概念？
我有一个类Person，它有两个属性 Name( String) 和 Weight( Integer)。
我想根据它们的权重以降序将元素存储在 PriorityQueue 中，即元素在队列中的顶部权重越高。
到目前为止我已经尝试过这个：
PriorityQueue<Person> personPriorityQueue = new PriorityQueue<Person>((a,b)-> Integer.compare(a.getWeight(), b.getWeight()));
personPriorityQueue.add(new Person(40,"N1"));
personPriorityQueue.add(new Person(60,"N2"));
personPriorityQueue.add(new Person(50,"N3"));
personPriorityQueue.forEach(s-> System.out.println(s.getName()));
我得到的输出是：
N1
N2
N3
我应该得到：
N2
N3
N1