关于#java#的问题：为什么Java的PriorityQueue没有按优先级最小的输出啊

请问为什么Java的PriorityQueue没有按优先级最小的输出啊

public class HuffmanNode implements Comparable<HuffmanNode>{
    public char c;
    public int frequency = 0;

    public HuffmanNode(char c){
        this.c = c;
        frequency++;
    }


//    给优先级队列比较大小
    @Override
    public int compareTo(HuffmanNode o) {
        return this.frequency - o.frequency;
    }

    @Override
    public String toString() {
        return  c + " : " + frequency;
    }
}


import java.util.PriorityQueue;

//question 8.5 编写程序实现哈弗曼编码和解码
public class Huffman {

    private String text;

    public Tree huffmanTree;


    public Huffman(String text){
        this.text = text;
        CreateHuffmanTree(text);
    }

    private void CreateHuffmanTree(String text){
        PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();
        int length = text.length();
        char a;
        boolean b;

        for (int i = 0; i < length; i++) {
            a = text.charAt(i);
            b = false;
            for (HuffmanNode huffmanNode : priorityQueue) {
                if (huffmanNode.c == a) {
                    huffmanNode.frequency++;
                    b = true;
                }
            }

            if (!b){
                priorityQueue.offer(new HuffmanNode(a));
            }
        }

        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());


    }


    public static void main(String[] args) {
        String text = "Accept a text message,possible of more than one line." +
                "Create a Huffman tree for this message." +
                "Create a code table." +
                "Encode the message into binary." +
                "Decode the message form binary back to text.";

        Huffman huffman = new Huffman(text);

    }

输出是这样的：
p和C的输出顺序不对

A : 1
, : 1
u : 1
E : 1
D : 1
k : 1
p : 2                                        
H : 1
x : 2
y : 2
l : 3
d : 3
g : 4
C : 2
h : 4
f : 5
. : 5
b : 5
c : 6
i : 6
m : 7
r : 8
n : 8
s : 11
o : 11
a : 15
t : 15
  : 28
e : 28

问题在于你入队之后又修改了优先级对应的值，等于破坏了这个结构的约定（它内部是用堆来实现的）。
应该是将所有单词频率统计完成后再进行入队操作。

如果想简单改（不优雅），可以加个构造函数和equals，再改造下for循环，应该就能凑合用了：
（改hashcode可参考书effective java，compareTo也需要优化）

    public HuffmanNode(char c, int frequency) {
        this.c = c;
        this.frequency = frequency;
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof HuffmanNode) {
            return ((HuffmanNode)o).c == this.c;
        }
        return false;
    }

改造for

        for (int i = 0; i < length; i++) {
            a = text.charAt(i);
            int freq = 0;
            for (HuffmanNode huffmanNode : priorityQueue) {
                if (huffmanNode.c == a) {
                    freq = ++huffmanNode.frequency;
                    break;
                }
            }

            if (freq == 0) {
                priorityQueue.offer(new HuffmanNode(a));
            } else {
                priorityQueue.remove(new HuffmanNode(a));
                priorityQueue.offer(new HuffmanNode(a, freq));
            }
        }

【以下回答由 GPT 生成】

问题的原因是在自定义的比较器中返回的是频率的差值，而不是当前节点频率和参数节点频率的差值。这导致PriorityQueue在进行优先级比较时产生了错误的结果，所以输出的顺序不是按照优先级最小的顺序。

解决该问题的方法是在自定义的比较器中返回当前节点频率和参数节点频率的差值。

修改HuffmanNode类的compareTo方法如下：

@Override
public int compareTo(HuffmanNode o) {
    return this.frequency - o.frequency;
}

然后就可以按照优先级最小的顺序输出PriorityQueue中的元素了。

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7508833
• 这篇博客也不错, 你可以看下Java中PriorityQueue的排序
• 除此之外, 这篇博客: java堆和优先级队列PriorityQueue的使用及实现中的 优先级队列PriorityQueue 部分也许能够解决你的问题。