哈夫曼编码贪心算法伪代码java实现

以下是哈夫曼编码贪心算法的伪代码和Java实现：

伪代码：

1. 初始化一个优先队列（最小堆）Q，将所有字符和它们的频率添加到队列中。
2. while(Q.size()>1) do:
a. 从Q中删除两个频率最低的节点，将它们合并成一个新的节点。
b. 将新节点添加到Q中。
3. 根据生成的哈夫曼树，为每个字符生成哈夫曼编码。

Java实现：

import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.HashMap;

public class HuffmanCoding {

    // 定义内部节点类
    private static class Node {
        char c;
        int freq;
        Node left;
        Node right;
        
        public Node(char c, int freq) {
            this.c = c;
            this.freq = freq;
        }
    }

    // 定义比较器，用于优先队列中节点的排序
    private static class NodeComparator implements Comparator<Node> {
        public int compare(Node n1, Node n2) {
            return n1.freq - n2.freq;
        }
    }

    // 生成哈夫曼编码
    public static HashMap<Character, String> generateHuffmanCode(String text) {
        // 统计字符频率
        HashMap<Character, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        // 构建哈夫曼树
        PriorityQueue<Node> pq = new PriorityQueue<>(new NodeComparator());
        for (char c : freqMap.keySet()) {
            pq.offer(new Node(c, freqMap.get(c)));
        }
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node('\0', left.freq + right.freq);
            parent.left = left;
            parent.right = right;
            pq.offer(parent);
        }
        Node root = pq.poll();

        // 生成哈夫曼编码
        HashMap<Character, String> codeMap = new HashMap<>();
        generateCode(root, new StringBuilder(), codeMap);
        return codeMap;
    }

    // 递归生成哈夫曼编码
    private static void generateCode(Node node, StringBuilder prefix, HashMap<Character, String> codeMap) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            codeMap.put(node.c, prefix.toString());
        } else {
            prefix.append('0');
            generateCode(node.left, prefix, codeMap);
            prefix.deleteCharAt(prefix.length() - 1);

            prefix.append('1');
            generateCode(node.right, prefix, codeMap);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }
}