霍夫曼编码树 - 优先级队列故障

Question

我正在尝试编写一个程序来计算字符串中每个字符的霍夫曼代码。

这是我的代码::

import java.util.Collections;
import java.util.PriorityQueue;

public class HuffmanCode{
    PriorityQueue<Node> queue = new PriorityQueue<Node>();
    PriorityQueue<Node> queueCopy = new PriorityQueue<Node>();

    public void getCodes(String text) {
        int[] count = countOccurences(text);
        fillQueue(count);
        makeHuffmanTree();
        assignCodes();
        displayCodes();
    }

    public int[] countOccurences(String text) {
        int[] letters = new int[256];
        for(int i = 0; i < text.length(); i++) {
            letters[(int)(text.charAt(i))]++;
        }
        return letters;
    }

    public void fillQueue(int[] count) {
        for(int i = 0; i < count.length; i++) {
            if(count[i] != 0) {
                queue.offer(new Node((char)i, count[i]));
                queueCopy.offer(new Node((char)i, count[i]));
            }
        }
    }

    public void makeHuffmanTree() {
        if(queue.size() > 1) {
            Node node1 = queue.remove();
            Node node2 = queue.remove();
            queue.offer(new Node(node1, node2));
            makeHuffmanTree();
        }
    }

    public void assignCodes() {
        assignCodes(queue.remove(), "");
    }

    public void assignCodes(Node root, String code) {
        if(root.left != null) 
            assignCodes(root.left, code + "0");
        if(root.right!= null) 
            assignCodes(root.right, code + "1");
        if(root.left == null && root.right == null)
            root.code = code + "";
    }

    public void displayCodes() {
        for(Node n: queue)
            System.out.println(n.character + " -> " + n.weight + " -> " + n.code);
    }
}

这是 Node class::

public class Node implements Comparable<Node>{
    char character;
    int weight;
    Node left;
    Node right;
    String code = "";

    Node(char character, int weight) {
        this.character = character;
        this.weight = weight;
    }

    Node(Node node1, Node node2) {
        weight = node1.weight + node2.weight;
        left = node1;
        right = node2;
    }

        }@Override
    public int compareTo(Node e) {
        if(this.weight < e.weight)
            return -1;
        else if(this.weight == e.weight)
            return 0;
        else
            return 1;
    }
}

如果调试上面的代码，您会注意到 queue 中的元素没有正确排序。例如，如果 text 是 'Mississipi'，则 queue 包含 M,i,p,s - 这是错误的（因为，M 出现了一次，i发生了 4 次，p 一次，s 发生了 4 次）。应该是M,p,s,i.

更新

我将 compareTo 方法替换为：

@Override
public int compareTo(Node e) {
if(this.weight < e.weight)
    return 1;
else if(this.weight == e.weight)
    return 0;
else
    return -1;
}

现在，虽然顺序与要求相反，但排序是正确的。这次，当我输入 Mississipi 时， queue 包含 'i,s,p,M'

Answer 1

来自 PriorityQueue

的 Javadoc

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

并且对于 PriorityQueue.iterator()

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

如果你想要一个排序的结构，你可以使用 TreeSet。

霍夫曼编码树 - 优先级队列故障

Huffman coding tree - Priority queue malfunctioning

java

priority-queue

huffman-code