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 = new TreeNodeHuffman('a', 8167); TreeNodeHuffman o = new TreeNodeHuffman('o', 7507); TreeNodeHuffman i = new TreeNodeHuffman('i', 6966); TreeNodeHuffman n = new TreeNodeHuffman('a', 6749); TreeNodeHuffman s = new TreeNodeHuffman('s', 6327); TreeNodeHuffman h = new TreeNodeHuffman('h', 6094); TreeNodeHuffman r = new TreeNodeHuffman('r', 5987); TreeNodeHuffman d = new TreeNodeHuffman('d', 4253); TreeNodeHuffman l = new TreeNodeHuffman('l', 4025); TreeNodeHuffman c = new TreeNodeHuffman('c', 2782); TreeNodeHuffman u = new TreeNodeHuffman('u', 2758); TreeNodeHuffman m = new TreeNodeHuffman('m', 2406); TreeNodeHuffman w = new TreeNodeHuffman('w', 2360); TreeNodeHuffman f = new TreeNodeHuffman('f', 2228); TreeNodeHuffman g = new TreeNodeHuffman('g', 2015); TreeNodeHuffman y = new TreeNodeHuffman('y', 1974); TreeNodeHuffman p = new TreeNodeHuffman('p', 1929); TreeNodeHuffman b = new TreeNodeHuffman('b', 1492); TreeNodeHuffman v = new TreeNodeHuffman('v', 978); TreeNodeHuffman k = new TreeNodeHuffman('k', 772); TreeNodeHuffman j = new TreeNodeHuffman('j', 153); TreeNodeHuffman x = new TreeNodeHuffman('x', 150); TreeNodeHuffman q = new TreeNodeHuffman('q', 95); TreeNodeHuffman z = new TreeNodeHuffman('z', 74); PriorityQueue queue = new PriorityQueue(26, compare); queue.add(e); queue.add(t); queue.add(a); queue.add(o); queue.add(i); queue.add(n); queue.add(s); queue.add(h); queue.add(r); queue.add(d); queue.add(l); queue.add(c); queue.add(u); queue.add(m); queue.add(w); queue.add(f); queue.add(g); queue.add(y); queue.add(p); queue.add(b); queue.add(v); queue.add(k); queue.add(j); queue.add(x); queue.add(q); queue.add(z); System.out.println(queue); } } 

输出如下：[z，k，q，g，v，x，u，d，f，y，b，m，j，i，c，e，s，o，w，a，r，h ，p，t，l，a]。 但是，输出应该是[z，q，x，j，k，v，b ……..]。 提前致谢！

Answer 1

您需要逐个轮询PriorityQueue的项目。 toString不会这样做。

而不是你的System.out.println(queue); 做这个：

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

原因是PriorityQueue永远不会在内部完全排序，查找堆如何工作以获取更多细节。 从中调查项目会在调用期间修复堆，因此它应该按排序顺序输出元素。

Answer 2

System.out.println(queue)正在打印未排序的队列。 如果要打印队列实际订单，请按照下面的代码使用poll来从队列的顶部到底部获取元素：

 TreeNodeHuffman tn = null; do{ tn = queue.poll(); if(tn!=null){ System.out.print(tn.key+","); } }while(tn != null); 

并且您将按预期看到此输出：

Z，Q，X，J，K，V，B，P，Y，G，F，W，M，U，C，L，d，R，H，S，A，I，O，A，T， E，

Answer 3

你希望更低的频率更高，所以：

  public int compare(TreeNodeHuffman p1, TreeNodeHuffman p2) { if (p1.frequency < p2.frequency) return 1; if (p1.frequency > p2.frequency) return -1; return 0; } } 

如果要测试它，请将其发送到单线程池并查看正在处理的作业的顺序，而不是字符串或迭代器。 正如doc在http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#iterator%28%29上所说：

返回此队列中元素的迭代器。 迭代器不会以任何特定顺序返回元素。

可以查看http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Executors.html#newSingleThreadExecutor%28%29以获取快速单线程池来测试它。

Answer 4

@Thomas回答有效。

我的方法是在不实际清空队列的情况下产生相同的结果。 所以，我在PriorityQueue创建了一个包装器，并为它实现了next()和hasNext() 。 此外，要精确模拟优先级队列行为，请通过PriorityQueue对象extend AbstractQueue并将调用委托给offer ， peek ， poll和size等方法。

 priorityQueueObject.methodName() 

免责声明：这会将整个队列复制到一个列表并对其进行排序。

 public class MyPriorityQueue, T> extends AbstractQueue { Integer arrOfInts[] = { 11, 7, 15, 10, 2, 1, 4, 5, 7, 2, 18, 1, 19}; PriorityQueue pq = new PriorityQueue<>(); public static void main(String[] args) { MyPriorityQueue mpq = new MyPriorityQueue<>(); mpq.addAll(Arrays.asList(arrOfInts)); //Using iterator Iterator it = mpq.iterator(); System.out.println("The internal priority queue:" + mpq.pq); System.out.println("Using Iterator:"); while(it.hasNext()) { System.out.print(it.next() + ", "); } System.out.println("\nUsing simple system out println:"); System.out.println(mpq); System.out.println("Using foreach: "); for(Object o : mpq) { System.out.print(o + ", "); } } @Override public boolean offer(E arg0) { return pq.offer(arg0); } @Override public E peek() { return pq.peek(); } @Override public E poll() { return pq.poll(); } @Override public Iterator iterator() { ArrayList list = new ArrayList(Arrays.asList(pq.toArray())); Collections.sort(list, null); return new Iterator() { @Override public boolean hasNext() { return !list.isEmpty(); } @Override public E next() { assert (hasNext()); return list.remove(0); } }; } @Override public int size() { return pq.size(); } } 

打印：

 The internal priority queue:[1, 2, 1, 7, 5, 2, 4, 11, 7, 10, 18, 15, 19] Using Iterator: 1, 1, 2, 2, 4, 5, 7, 7, 10, 11, 15, 18, 19, Using simple system out println: [1, 1, 2, 2, 4, 5, 7, 7, 10, 11, 15, 18, 19] Using foreach: 1, 1, 2, 2, 4, 5, 7, 7, 10, 11, 15, 18, 19,