栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

贪心法/哈夫曼编码

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

贪心法/哈夫曼编码

贪心法

贪心准则:每次从队列中取出最大和次大的两个结点,权重相加之后构成新的结点后放入队列中
最优性原理:最优子结构问题,子问题也是哈夫曼编码问题,对子问题的求解等价于对大问题的求解

哈夫曼编码

哈夫曼树只有度为0的结点和度为2的结点
已知公式n0=n2+1,叶子结点有n个时,度为2的结点有n-1个
使用静态链表存储哈夫曼树时需要存储n个叶子结点,n-1个度为2的结点,共需要2n-1长度的静态链表
所谓静态链表即用顺序表(数组)模拟链表,使用数组下标模拟结点地址指针
哈夫曼树是最优二叉树,最优二叉树是带权路径长度最短的树
过程:每次从队列中取出最大和次大的两个结点,权重相加之后构成新的结点后放入队列中

代码
package xcrj.kchalgorithm.greedy;

import java.util.*;


public class HuffmanCoding {
    
    static class HuffmanTreeNode {
        // 结点字符
        private char data;
        // 权值
        private int weight;
        // 父节点
        private int parent;
        // 左孩子结点
        private int leftChild;
        // 右孩子结点
        private int rightChild;
    }

    
    static class Node implements Comparable {
        // 对应哈夫曼树中结点位置
        private int no;
        // 字符
        private char data;
        // 权值
        private int weight;

        
        @Override
        public int compareTo(Node o) {
            return this.weight >= o.weight ? 1 : -1;
        }
    }

    // 字符数量
    private static int n = 5;
    
    private static HuffmanTreeNode[] huffmanTreeNodes = new HuffmanTreeNode[2 * n - 1];

    static {
        // 数组里面预留了引用空间,但没有具体引用对象
        for (int i = 0; i < 2 * n - 1; i++) {
            huffmanTreeNodes[i] = new HuffmanTreeNode();
        }
    }

    // 存放每个字符的哈夫曼编码
    private static Map huffmanCode = new HashMap<>(n);

    
    public static void createHuffmanTree(char[] datas, int[] weights) {
        // 初始化叶子结点数据和权重
        for (int i = 0; i < n; i++) {
            huffmanTreeNodes[i].data = datas[i];
            huffmanTreeNodes[i].weight = weights[i];
        }

        // 所有哈夫曼结点:设置2*n-1个哈夫曼结点的指针域
        for (int i = 0; i < 2 * n - 1; i++) {
            huffmanTreeNodes[i].parent = -1;
            huffmanTreeNodes[i].leftChild = -1;
            huffmanTreeNodes[i].rightChild = -1;
        }

        // 优先级队列
        PriorityQueue priorityQueue = new PriorityQueue<>(n);

        // n个叶子结点:将n个叶子结点进优先级队列,构建小根堆
        for (int j = 0; j < n; j++) {
            Node node = new Node();
            node.no = j;
            node.data = huffmanTreeNodes[j].data;
            node.weight = huffmanTreeNodes[j].weight;
            priorityQueue.add(node);
        }
        
        for (int k = n; k < 2 * n - 1; k++) {
            // 从优先级队列中取出 最大和次大的两个结点
            Node leftChild = priorityQueue.remove();
            Node rightChild = priorityQueue.remove();
            // 放入哈夫曼树,静态链表存储“最优二叉树”
            huffmanTreeNodes[k].weight = leftChild.weight + rightChild.weight;
            huffmanTreeNodes[k].leftChild = leftChild.no;
            huffmanTreeNodes[k].rightChild = rightChild.no;
            huffmanTreeNodes[leftChild.no].parent = k;
            huffmanTreeNodes[rightChild.no].parent = k;
            // 将权重相加后的结点 放入优先级队列
            Node node = new Node();
            node.no = k;
            node.weight = leftChild.weight + rightChild.weight;
            priorityQueue.add(node);
        }
    }

    
    public static void createHuffmanCode() {
        // n个叶子结点才有哈夫曼编码
        for (int i = 0; i < n; i++) {
            // 存储编码结果
            StringBuilder code = new StringBuilder(5);
            code.append("");
            // 记录当前游标和父游标
            int nowNo = i;
            int preNo = huffmanTreeNodes[nowNo].parent;
            // 从叶子结点往前根节点走
            while (preNo != -1) {
                // 左孩子,左0
                if (huffmanTreeNodes[preNo].leftChild == nowNo) code.append("0");
                    // 右孩子,右1
                else code.append("1");
                // 继续往根节点走
                nowNo = preNo;
                preNo = huffmanTreeNodes[nowNo].parent;
            }
            // 存储每个叶子结点的哈夫曼编码
            huffmanCode.put(huffmanTreeNodes[i].data, code.reverse().toString());
        }
    }

    public static void main(String[] args) {
        char[] datas = {'A', 'B', 'C', 'D', 'E'};
        int[] weights = {4, 2, 1, 7, 3};
        createHuffmanTree(datas, weights);
        createHuffmanCode();
        System.out.println(huffmanCode);
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/958972.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号