贪心算法哈夫曼编码java

贪心算法哈夫曼编码是一种基于贪心思想的数据压缩算法。下面是实现哈夫曼编码的Java代码：

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

class HuffmanNode {
    char c;
    int freq;
    HuffmanNode left, right;
}

class MyComparator implements Comparator<HuffmanNode> {
    public int compare(HuffmanNode x, HuffmanNode y) {
        return x.freq - y.freq;
    }
}

public class HuffmanCode {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String text = input.nextLine().trim();
        HashMap<Character, Integer> frequency = new HashMap<>();
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (frequency.containsKey(c)) {
                frequency.put(c, frequency.get(c) + 1);
            } else {
                frequency.put(c, 1);
            }
        }
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(new MyComparator());
        for (char c : frequency.keySet()) {
            HuffmanNode node = new HuffmanNode();
            node.c = c;
            node.freq = frequency.get(c);
            node.left = null;
            node.right = null;
            pq.add(node);
        }
        while (pq.size() > 1) {
            HuffmanNode node1 = pq.poll();
            HuffmanNode node2 = pq.poll();
            HuffmanNode newNode = new HuffmanNode();
            newNode.freq = node1.freq + node2.freq;
            newNode.c = '-';
            newNode.left = node1;
            newNode.right = node2;
            pq.add(newNode);
        }
        HuffmanNode root = pq.peek();
        HashMap<Character, String> codes = new HashMap<>();
        encode(root, "", codes);
        for (char c : codes.keySet()) {
            System.out.println(c + ": " + codes.get(c));
        }
    }

    private static void encode(HuffmanNode node, String code, HashMap<Character, String> codes) {
        if (node == null) {
            return;
        }
        if (node.c != '-') {
            codes.put(node.c, code);
        }
        encode(node.left, code + "0", codes);
        encode(node.right, code + "1", codes);
    }
}

代码中使用了优先队列来存储哈夫曼树的节点，并且定义了一个比较器来按照节点权重来进行优先级排序。在主函数中，首先统计了字符串中每个字符的出现频率，然后把每个字符和对应的频率封装成节点放入优先队列中。然后通过循环，不断取出优先队列中最小的两个节点，合并成一个新节点，并且把这个新节点放入优先队列中。最终，优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。接着，利用递归的方法，对哈夫曼树进行遍历，生成每个字符对应的编码，并存储在一个HashMap中。最后，输出每个字符和对应的编码。