为什么 PriorityQueue.toString 返回错误的元素顺序? [英] Why does PriorityQueue.toString return the wrong element order?

问题描述

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

I am trying to make a priority queue in java with the nodes with the lowest frequency in priority. However, my comparator is not working and the output is very weird. I believe I need to change my comparator but I am not sure how to change it. Here is my code:

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].

The output is as follows: [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........].

However, the output should be [z, q, x, j, k, v, b........].

推荐答案

您需要从 PriorityQueue 中一一轮询项目.toString 不这样做.

You need to poll the items from the PriorityQueue one by one. toString doesn't do that.

所以代替你的 System.out.println(queue); 这样做:

So instead of your System.out.println(queue); do this:

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

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

The reason is that the PriorityQueue is never completely sorted internally, lookup how a heap works for more detail. Polling items from it fixes the heap during the calls, thus it should output the elements in sorted order.

这篇关于为什么 PriorityQueue.toString 返回错误的元素顺序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！