哈夫曼编码

/**
 * @author Howl
 * 哈夫曼编码
 */
public class HuffmanCode {
    /**
     * 哈夫曼树结点结构
     */
    private static class Node implements Comparable<Node> {
        /**
         * 权值、二进制编码0、1、左右孩子
         */
        int weight;
        String code;
        Node left;
        Node right;

        Node(int weight) {
            this.weight = weight;
        }

        Node(int weight, Node left, Node right) {
            this.weight = weight;
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight, o.weight);
        }
    }

    /**
     * 根节点、存储全部节点
     */
    private Node root;
    private static Node[] nodes;

    /**
     * 构建哈夫曼树
     * 建树是从最小权值开始的，所以借助小根堆
     */
    public void createHuffman(int[] weights) {

        // 构建小根堆，弹出是最小的元素
        Queue<Node> nodeQueue = new PriorityQueue<>();
        nodes = new Node[weights.length];
        for (int i = 0; i < weights.length; i++) {
            nodes[i] = new Node(weights[i]);
            nodeQueue.add(nodes[i]);
        }

        // 节点队列只剩一个节点结束，即根节点构建完成
        while (nodeQueue.size() > 1) {

            // 弹出权值最小的两个结点
            Node left = nodeQueue.poll();
            Node right = nodeQueue.poll();

            // 创建新节点作为两结点的父节点
            Node parent = new Node(left.weight + right.weight, left, right);
            nodeQueue.add(parent);
        }

        // 哈夫曼树根，遍历要用，优先级队列GC
        root = nodeQueue.poll();
        // 实现编码
        encode();
    }

    /**
     * 输入字符下标，输出对应的哈夫曼编码
     */
    public String convertHuffmanCode(int index) {
        return nodes[index].code;
    }

    /**
     * 递归填充二进制编码
     */
    private void encode() {
        encode(root, "");
    }

    private void encode(Node node, String code) {
        if (node == null) {
            return;
        }
        node.code = code;
        encode(node.left, node.code + "0");
        encode(node.right, node.code + "1");
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        // 字符及其对应权值
        char[] chars = {'A', 'B', 'C', 'D', 'E', 'F'};
        int[] weights = {2, 3, 7, 9, 18, 25};

        HuffmanCode huffManCode = new HuffmanCode();
        huffManCode.createHuffman(weights);
        for (int i = 0; i < chars.length; i++) {
            System.out.println(chars[i] + ":" + huffManCode.convertHuffmanCode(i));
        }
    }
}

// 图片压缩
Thumbnails.of("C:\\Users\\Howl\\Desktop\\InPic.png")	// 输入图片地址
    .scale(1)											// 和原尺寸大小，即长度，1是原大小
    .outputQuality(0.5)									// 和原图的质量
    .outputFormat("jpg")								// 输出格式，png为高保真不会压缩
    .toFile("C:\\Users\\Howl\\Desktop\\OutPic");		// 输出地址
}