哈夫曼编码算法实现-白红宇

哈夫曼编码算法实现

阅读量：3952 次

发布时间：2019-05-24

本文共 2362 字，大约阅读时间需要 7 分钟。

package juc;import lombok.ToString;import java.util.HashMap;import java.util.Map;import java.util.PriorityQueue;/** * @Author lyr * @create 2020/10/28 19:43 */public class Main {
       /**     * @param args     */    public static void main(String[] args) {
           // TODO Auto-generated method stub        System.out.println("hello world");        double[] p = {
   0.35, 0.1, 0.2, 0.2, 0.15};        char[] q = {
   'a', 'b', 'c', 'd', '-'};        PriorityQueue
   
     pq = new PriorityQueue<>((node1, node2) ->        {
               int x = Double.compare(node1.freq,node2.freq);            if (x!=0) return x;            //按照字典序排序            return Character.compare(node1.value,node2.value);                   });        for (int i = 0; i < p.length; ++i) {
               double freq = p[i];            char value = q[i];            Node node = new Node(value, freq);            node.isLeaf = true;            pq.offer(node);        }        while (pq.size() > 1) {
               Node min1 = pq.poll();            Node min2 = pq.poll();            double freq = min1.freq + min2.freq;            Node root = new Node('&', freq);            root.left = min1;            root.right = min2;            pq.offer(root);        }        //pq.size() ==1        Node root = pq.poll();        Map
    
      map = printCode(new HashMap<>(),root,"");        // System.out.println(map);        map.forEach((node, code) ->{
               System.out.println(node.value +"="+code);        });    }    static Map
     
       printCode(Map
      
        map, Node node, String parentCode) {
           if(node == null) return map;        if (node.isLeaf) {
               map.put(node,parentCode);        }        printCode(map,node.left,parentCode+"0");        printCode(map,node.right,parentCode+"1");        return map;    }    @ToString    static class Node {
           double freq;        Node left;        Node right;        char value;        boolean isLeaf;        @Override        public int hashCode() {
               int result;            long temp;            temp = Double.doubleToLongBits(freq);            result = (int) (temp ^ (temp >>> 32));            result = 31 * result + (int) value;            return result;        }        Node(char value, double freq) {
               this.freq = freq;            this.value = value;        }    }}