一、大顶堆和小顶堆
1. 特征
二、赫夫曼树
1. 逻辑思维
wpl = 该节点距离root的长度*节点值
所有的wpl最小
2. 代码实现
1. node类 显示Comparable接口,以便进行比较
2. 将原Array 改为ArrayList的列表
3. 进行取值/增删
package com.atguigu.huffmanTree;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import static java.util.Collections.*;
public class HuffmanTreeDemo {
public static void main(String[] args) {
int[] arr = {13,7,8,3,29,6,1};
Node resNode = createHuffmanTree(arr);
System.out.println(resNode);
}
// 创建赫夫曼树的方法
public static Node createHuffmanTree(int[] arr){
//第一步: 为了操作方便,将元素改为node的对象
// 1. 遍历arr数组
// 2. 将arr的每个元素构成一个Node
// 3. 将node放入到arrayList中
List<Node> nodes = new ArrayList<Node>();
for (int value : arr) {
nodes.add(new Node(value));
}
while(nodes.size()>1) {
// 从小到达排序
Collections.sort(nodes);
System.out.println(nodes.toString());
// 取出根节点全职最小的2颗二叉树
Node left = nodes.get(0);
// 取出第二小的节点
Node right = nodes.get(1);
// 构建一颗新的二叉树
Node parent = new Node(left.value + right.value);
parent.left = left;
parent.right = right;
//从arrayList中删除原来的前2个节点
nodes.remove(0);
nodes.remove(0);
nodes.add(parent);
}
return nodes.get(0);
}
}
// 创建节点类
// 因为涉及到了排序,所以让其继承Collection,实现comparable接口
class Node implements Comparable {
int value;
Node left; // 左子节点
Node right; // 右子节点
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
", left=" + left +
", right=" + right +
'}';
}
@Override
public int compareTo(Object o) {
Node o1 = (Node) o;
// 从小到大
return this.value-o1.value;
}
}
三、赫夫曼编码
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);
}