为什么 PriorityQueue.toString return 元素顺序错误？

Question

我正在尝试在 java 中使用优先级频率最低的节点创建一个优先级队列。但是，我的比较器不工作，输出很奇怪。我相信我需要更改我的比较器，但我不确定如何更改它。这是我的代码：

public class HuffmanComparator implements Comparator<TreeNodeHuffman> {
    public int compare(TreeNodeHuffman p1, TreeNodeHuffman p2) {
        if (p1.frequency < p2.frequency) return -1;
        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<TreeNodeHuffman> queue = new PriorityQueue<TreeNodeHuffman>(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 , 一个].

但是，输出应该是[z, q, x, j, k, v, b.......]。

Answer 1

你想让低频变得更高所以:

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

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

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

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

Answer 2

您需要逐一轮询 PriorityQueue 中的项目。 toString 不会那样做。

所以不要 System.out.println(queue); 这样做：

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

原因是 PriorityQueue 从未在内部完全排序，请查看堆的工作原理以获取更多详细信息。从中轮询项目会在调用期间修复堆，因此它应该按排序顺序输出元素。

Answer 3

System.out.println(queue) 正在打印未排序的队列。如果要打印队列的实际顺序，请遵循以下代码，该代码使用轮询从队列的顶部到底部获取元素：

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 4

@Thomas 回答有效。

我的方法是在不实际清空队列的情况下产生相同的结果。因此，我在 PriorityQueue 上创建了一个包装器，并为其实现了 next() 和 hasNext()。此外，为了准确模拟优先级队列行为，extend AbstractQueue 和 delegate 调用 offer、peek、poll 和 size 通过 PriorityQueue 对象。

priorityQueueObject.methodName()

免责声明：这确实需要将整个队列复制到列表中并对其进行排序。

public class MyPriorityQueue<E extends Comparable<T>, T> extends AbstractQueue<E> { Integer arrOfInts[] = { 11, 7, 15, 10, 2, 1, 4, 5, 7, 2, 18, 1, 19}; PriorityQueue<E> 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<E> iterator() { ArrayList<E> list = new ArrayList(Arrays.asList(pq.toArray())); Collections.sort(list, null); return new Iterator<E>() { @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,

为什么 PriorityQueue.toString return 元素顺序错误？

Why does PriorityQueue.toString return the wrong element order?

java

printing

sorting

priority-queue

comparator