为什么PriorityQueue。toString返回错误的元素顺序？[副本]

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， a]。

然而，输出应为[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() :

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

可以看到http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Executors.html#newSingleThreadExecutor（）以获得一个快速的单线程池来测试这一点。

Answer 2

匿名用户

系统。出来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 3

您需要逐个轮询PriorityQueue中的项目<代码>toString不能这样做。

因此，不要使用您的系统。出来println（队列） 执行此操作：

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

原因是优先级队列（PriorityQueue）在内部从未完全排序，请查看堆的工作方式以获取更多详细信息。来自它的轮询项在调用期间固定堆，因此它应该按排序顺序输出元素。