一、大顶堆和小顶堆

1. 特征

  • 完全二叉树；
  • 用数组的形式存放二叉树；将数组的下标与二叉树的形式对应起来； arr[x] 的左子树是arr[2x+1], 右子树是arr[2x+2]

    2. 基本思想

二、赫夫曼树

1. 逻辑思维

wpl = 该节点距离root的长度*节点值
所有的wpl最小

2. 代码实现

1. node类 显示Comparable接口，以便进行比较

2. 将原Array 改为ArrayList的列表

3. 进行取值/增删

  1. package com.atguigu.huffmanTree;
  3. import java.util.ArrayList;
  4. import java.util.Collection;
  5. import java.util.Collections;
  6. import java.util.List;
  8. import static java.util.Collections.*;
  10. public class HuffmanTreeDemo {
  11.     public static void main(String[] args) {
  12.         int[] arr = {13,7,8,3,29,6,1};
  13.         Node resNode = createHuffmanTree(arr);
  14.         System.out.println(resNode);
  16.     }
  17.     // 创建赫夫曼树的方法
  18.     public static Node createHuffmanTree(int[] arr){
  19.         //第一步： 为了操作方便，将元素改为node的对象
  20.         // 1. 遍历arr数组
  21.         // 2. 将arr的每个元素构成一个Node
  22.         // 3. 将node放入到arrayList中
  23.         List<Node> nodes = new ArrayList<Node>();
  24.         for (int value : arr) {
  25.             nodes.add(new Node(value));
  26.         }
  28.         while(nodes.size()>1) {
  29.             // 从小到达排序
  30.             Collections.sort(nodes);
  31.             System.out.println(nodes.toString());
  32.             // 取出根节点全职最小的2颗二叉树
  33.             Node left = nodes.get(0);
  34.             // 取出第二小的节点
  35.             Node right = nodes.get(1);
  36.             // 构建一颗新的二叉树
  37.             Node parent = new Node(left.value + right.value);
  38.             parent.left = left;
  39.             parent.right = right;
  40.             //从arrayList中删除原来的前2个节点
  41.             nodes.remove(0);
  42.             nodes.remove(0);
  43.             nodes.add(parent);
  44.         }
  45.         return nodes.get(0);
  46.     }
  47. }
  49. // 创建节点类
  50. // 因为涉及到了排序，所以让其继承Collection，实现comparable接口
  51. class Node implements Comparable {
  52.     int value;
  53.     Node left; // 左子节点
  54.     Node right; // 右子节点
  56.     public Node(int value) {
  57.         this.value = value;
  58.     }
  60.     @Override
  61.     public String toString() {
  62.         return "Node{" +
  63.                 "value=" + value +
  64.                 ", left=" + left +
  65.                 ", right=" + right +
  66.                 '}';
  67.     }
  69.     @Override
  70.     public int compareTo(Object o) {
  71.         Node o1 = (Node) o;
  72.         // 从小到大
  73.         return this.value-o1.value;
  74.     }
  75. }

三、赫夫曼编码

1. 原理

用赫夫曼树进行压缩文件

2. 代码实现

1. Node(data,权重，left,right)

2. 得到字符串对应的byte数组

String content = “i like like like java do you like the java”;
byte[] bytes =content.getBytes();

3. 编写一个方法，将准备构建赫夫曼树的node放入到List中

生成赫夫曼树对应的赫夫曼编码的思路：
    1. 将赫夫曼编码表存放在  Map<Byte,String> 的形式中，eg: 32->01, 97->100，1000->11000等等
    2. 生成赫夫曼编码表时，需要去拼接路径，定义一个StringBuilder 存储摸一个叶子节点的路径；

通过map的形式存放数据：

// 存储每个byte出现的次数---map[key,value];
        Map<Byte,Integer> counts = new HashMap<Byte, Integer>();
        for (byte b : bytes) {
            Integer count = counts.get(b);   //将字母转换成askII 码的形式了
            if(count==null){ // 说明还没有存放数据
                counts.put(b,1);
            }else {
                counts.put(b,count+1);
            }
        }

<br />赫夫曼编码

// 生成赫夫曼编码
    static StringBuilder stringBuilder = new StringBuilder();  // 存放路径信息，左子节点为0，右子节点为1
    static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();  // 将huffman编码表放入Map中， 32->01, 97->100

    /**
     * 将传入的node节点的所有叶子节点的赫夫曼编码存放haffmanCodes中
     * @param node 传入的节点，默认从根节点开始
     * @param code 代表路径，左边为0，右边为1
     * @param stringBuilder 拼接路径
     */
    private static void getCodes(Node node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        // 将code加入到stringBuilder2
        stringBuilder2.append(code);
        if(node!=null){
            // 如果node为空则不处理
            // 判断当前node是叶子节点还是非叶子节点
            if(node.data==null){ // 非叶子节点，递归处理
                // 向左递归则为0
                getCodes(node, "0", stringBuilder2);
                // 向右递归则为1
                getCodes(node, "1",stringBuilder2);
            }else {
                // 说明是叶子节点
                huffmanCodes.put(node.data, stringBuilder2.toString());
            }
        }
    }

赫夫曼树

// 完成赫夫曼树
    private static Node createHuffmanTree(List<Node> arr){
        while(arr.size()>1){
            // 排序,从小到大
            Collections.sort(arr);
            // 取出第一个最小的二叉树
            Node left = arr.get(0);
            Node right = arr.get(1);
            // 创建新的二叉树根节点
            Node root = new Node(null, left.weight+right.weight);
            // 将已经处理过的点移除
            arr.remove(left);
            arr.remove(right);
            arr.add(root);
        }
        // 返回到根节点
        return arr.get(0);
    }