问题描述
我正在尝试使用PriorityQueue实现堆，如下所示：
PriorityQueue<Node> heap = new PriorityQueue<Node>();
Set<String> allWords = codebook.getAllWords();
for(String word : allWords)
{
heap.add(new Node(word, codebook.getProbability(word)));
System.out.println(heap.toString());
}
我将Node定义为包含上述方法的同一类中的私有类。 节点定义为：
private static class Node implements Comparable
{
protected Node left;
protected Node right;
protected String name;
protected double frequency;
public Node(String n, double f)
{
name = n;
frequency = f;
}
public Node(double f, Node l, Node r)
{
frequency = f;
left = l;
right = r;
}
@Override
public int compareTo(Object arg0)
{
Node other = (Node)(arg0);
if(this.frequency < other.frequency)
{
System.out.println(name + " < " + other.name);
return -1;
}
else if(this.frequency > other.frequency)
{
System.out.println(name + " > " + other.name);
return 1;
}
System.out.println(name + " is equal to " + other.name);
return 0;
}
public String toString()
{return name;}
}
但是，当我向PriorityQueue添加节点时，它们不按频率排序。 根据我的println语句的输出，Node.compareTo（）返回正确的值。 例如，给定数据集：
- 名称，频率
- 需要，3
- 猫，1
- 整洁，2
我的代码产生：
//添加需求
[需要]
//添加猫
猫<需要
[猫，需要]
//添加整洁
整洁>猫
[猫，需要，整洁]
当PriorityQueue应该是[cat，neat，need]
有关为什么会发生这种情况的任何提示？
1楼
来自的的顺序是未定义的;
调用poll()时的顺序应该是比较器排序。
根据API规范，
iterator()返回此队列中元素的迭代器。 迭代器不会以任何特定顺序返回元素。
如果您真正需要的是一个有序集，请使用SortedSet或将东西放入集合并使用Collections.sort() 。
但是，如果你真的需要一个pqueue，这是我的例子修复：
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
public class TestPriorityQueue
{
static Map<String,Double> codebook = new HashMap<String, Double>();
static {
codebook.put("need", 3.0);
codebook.put("cat", 1.0);
codebook.put("neat", 2.0);
}
public static void main(String[] args)
{
test();
}
public static void test() {
PriorityQueue<Node> heap = new PriorityQueue<Node>();
Set<String> allWords = codebook.keySet();
for (String word : allWords) {
heap.add(new Node(word, codebook.get(word)));
System.out.println(heap.toString());
}
System.out.println("In order now:");
while(!heap.isEmpty()) {
System.out.println(heap.poll());
}
}
private static class Node implements Comparable<Node>
{
protected Node left;
protected Node right;
protected String name;
protected double frequency;
public Node(String n, double f)
{
name = n;
frequency = f;
}
public Node(double f, Node l, Node r)
{
frequency = f;
left = l;
right = r;
}
@Override
public int compareTo(Node arg0)
{
if(this.frequency < arg0.frequency)
{
System.out.println(name + " < " + arg0.name);
return -1;
}
else if(this.frequency > arg0.frequency)
{
System.out.println(name + " > " + arg0.name);
return 1;
}
System.out.println(name + " is equal to " + arg0.name);
return 0;
}
public String toString()
{return name;}
}
}
得到：
[need]
cat < need
[cat, need]
neat > cat
[cat, need, neat]
In order now:
neat < need
cat
neat
need
2楼
PriorityQueues以“及时”为基础。 如果只显示其内容，则内容不会按排序顺序排列; 它们在一堆（自从你提到之后，我认为你已经知道了。）无论如何，要按顺序获取内容，你必须使用i poll（）逐个删除一个项目。