Tag: 优先级队列

将Java PriorityQueue转换为稳定的优先级队列: 我正在尝试在Java中实现稳定（先进先出）优先级队列。假设密钥是一个名称，值是一个年龄，我知道我可以像这样建立一个不稳定的优先级队列： Queue<Map.Entry> pq = new PriorityQueue<Map.Entry>(100, ageComparator); 这几乎可以满足我所需要的一切，除了它在我插入（或删除它们）时不保持键值对的顺序。我通过创建一个LinkedList找到了“解决方法”，它实际上提供了所有相同的function，除了它不包含带比较器选项的构造函数，我觉得它必须更慢，因为我保持值排序通过在每个队列操作后调用Collections.sort() 。所以我想我真的有两个选项让我感兴趣。首先，我如何编辑上面的PriorityQueue来维护插入和删除顺序？或者，我怎样才能强制我的LinkedList选项立即使用比较器而不必在每次操作时调用排序？谢谢！编辑：感谢发布的第一条评论中的好问题。通过FIFO，我的意思是对于具有相等值的键值对，应首先提取首先放入的对。

实现Java Comparator: 我正在尝试编写一个利用最小优先级队列的算法，所以我环顾谷歌并找到了PriorityQueue。看来，为了使用它，我需要告诉它我希望它如何优先排序，并且这样做的方法是使用比较器（我想比较我的“Node1”的特定数据字段）对象）。更多的谷歌搜索提出了创建一个新的比较器的想法，该比较器实现了比较器但覆盖了比较方法。我正在尝试的是这个（以及它的其他变体）： import java.util.Comparator; public class distComparator implements Comparator { @Override public int compare(Node1 x, Node1 y){ if(x.disty.dist){ return 1; } return 0; } } 编译器有几个理由抗议，其中一个原因是我没有超越比较器类（它说它是抽象的）错误：distComparator不是抽象的，并且不会覆盖Comparator中的抽象方法compare（Object，Object）我已将其切换为“比较（对象x，对象y）”，它负责处理该问题。此时虽然编译器抱怨它无法在x或y中找到“dist”变量 – 这是有道理的，因为它们是我的Node1类的一部分，而不是Object类。那怎么能起作用呢？它显然应该有Object类型，但是如何将它引导到正确的变量？

如何在方法调用之前将PriorityQueue恢复到其初始状态？: 我正在做练习问题练习IT Kth Smallest 这个问题基本上是你在PriorityQueue和某个k中传递的，你将返回该PriorityQueue中的第k个最小值。您还要将PriorityQueue还原到其初始状态，并可以使用一个堆栈或队列作为辅助数据结构。我的更高级别的伪思想是因为PriorityQueue已经充当了一个最小堆，从Java PriorityQueue ，我真正需要做的就是（我的算法）：从PriorityQueue中删除k个元素将第k个最小值存储为局部变量将删除的k元素推送到堆栈（堆栈，以便我可以按相同的顺序添加元素）弹出堆栈中的所有元素，然后将它们重新添加回PriorityQueue 返回第k个最小值以下是执行所有操作的代码： public int kthSmallest(PriorityQueue pQ, int k) { if(k pQ.size()) { throw new IllegalArgumentException(); } else { Stack aux = new Stack(); int kThSmallest = -1; for(int c=0;c<k;c++){ int element = pQ.remove(); if(c == k-1) kThSmallest = element; aux.push(element); } while(!aux.isEmpty()) pQ.add(aux.pop()); […]

PriorityQueue没有在添加上排序: 我有一个优先级队列，我在其中添加一个Node对象，其中节点应按其包含的值进行排序。出于某种原因，优先级队列不会对添加的节点进行排序。如果有人可以看到这个问题或有任何指导，我很感激。这是一个简短的例子： PriorityQueue PQ = new PriorityQueue(); //for each entry create a node and add it to the PriorityQueue for(Entry entry : entries){ PQ.add(new Node(entry.getKey(),entry.getValue(), true)); } 这是节点的compareTo方法： @Override public int compareTo(Node n) { if(n.frequency.intValue() > this.frequency.intValue()) return -1; else if(n.frequency.intValue() == this.frequency.intValue()) return 0; else return 1; }

编辑元素时重新排序Java优先级队列: 我正在尝试使用优先级队列来实现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 comparator = new VertexComparator(); […]

PriorityQueue.toString错误的元素顺序: 我试图在java中创建一个优先级最低的节点队列。但是，我的比较器不工作，输出非常奇怪。我相信我需要改变我的比较器，但我不知道如何改变它。这是我的代码： public class HuffmanComparator implements Comparator { public int compare(TreeNodeHuffman p1, TreeNodeHuffman p2) { if (p1.frequency p2.frequency) return 1; return 0; } } public class TreeNodeHuffman { public static void main(String[] args) { HuffmanComparator compare = new HuffmanComparator(); TreeNodeHuffman e = new TreeNodeHuffman(‘e’, 12702); TreeNodeHuffman t = new TreeNodeHuffman(‘t’, 9056); TreeNodeHuffman a […]