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

Question

请问为什么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

Answer 1

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

如果想简单改（不优雅），可以加个构造函数和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));
            }
        }