哈夫曼樹介紹
hello，大家好，我是bigsai。本以為哈夫曼樹、哈夫曼編碼很難，結果很容易嘛！
哈夫曼樹、哈夫曼編碼很多人可能聽過，但是可能并沒有認真學習了解，今天這篇就比較詳細的講一下哈夫曼樹。
首先哈夫曼樹是什麼？
哈夫曼樹的定義：給定N個權值作為N個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)，哈夫曼樹是帶權路徑長度最短的樹。權值較大的結點離根較近。
那這個樹長啥樣子呢？例如開始2，3，6，8，9權值節點構成的哈夫曼樹是這樣的：
從定義和圖上你也可以發現下面的規律：
- 初始節點都在樹的葉子節點上
- 權值大的節點離根更近
- 每個非葉子節點都有兩個孩子(因為我們自下向上構造，兩個孩子構成一個新樹的根節點)
你可能會好奇這麼一個哈夫曼樹是怎麼構造的，其實它是按照一個貪心思想和規則構造，而構造出來的這個樹的權值最小。這個規則下面會具體講解。
哈夫曼樹非常重要的一點：
WPL
(樹的所有葉結點的帶權路徑長度之和)。至于為什麼按照哈夫曼樹方法構造得到的權重最小,這裡不進行證明,但是你從局部來看(三個節點)也要權值大的在上一層WPL才更低。
WPL計算方法: WPL=求和(Wi * Li)其中Wi是第i個節點的權值(value)。Li是第i個節點的長(深)度.
例如上面 2，3，6，8，9權值節點構成的哈夫曼樹的WPL計算為(設根為第0層)：
比如上述哈夫曼樹的
WPL
為：
2*3+3*3+6*2+8*2+9*2=(2+3)*3+(6+8+9)*2=61
.
既然了解了哈夫曼樹的一些概念和WPL的計算方式，下面看看哈夫曼樹的具體構造方式吧！
哈夫曼樹構造
初始給一個森林有n個節點。我們主要使用貪心的思想來完成哈夫曼樹的構造：
- 在n個節點找到兩個最小權值節點(根)，兩個為葉子結構建構一棵新樹(根節點權值為左右孩子權值和)
- 先删掉兩個最小節點(n-2)個，然後加入建構的新節點(n-1)個
- 重複上面操作，一直到所有節點都被處理
在具體實作上，找到最小兩個節點需要排序操作，我們來看看2，6，8，9，3權值節點構成哈夫曼樹的過程。
初始時候各個節點獨立，先将其排序(這裡使用優先隊列)，然後選兩個最小節點(抛出)生成一個新的節點，再将其加入優先隊列中，此次操作完成後優先隊列中有5，6，8，9節點
重複上面操作，這次結束 隊列中有11，8，9節點(排序後8，9，11)
如果隊列為空，那麼傳回節點，并且這個節點為整個哈夫曼樹根節點root。
否則繼續加入隊列進行排序。重複上述操作，直到隊列為空。
在計算帶權路徑長度WPL的時候，需要重新計算高度(從下往上)，因為哈夫曼樹是從下往上構造的，并沒有以常量維護高度，可以構造好然後計算高度。
具體代碼實作
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class HuffmanTree {
public static class node
{
int value;
node left;
node right;
int deep;//記錄深度
public node(int value) {
this.value=value;
this.deep=0;
}
public node(node n1, node n2, int value) {
this.left=n1;
this.right=n2;
this.value=value;
}
}
private node root;//最後生成的根節點
List<node>nodes;
public HuffmanTree() {
this.nodes=null;
}
public HuffmanTree(List<node>nodes)
{
this.nodes=nodes;
}
public void createTree() {
Queue<node>q1=new PriorityQueue<node>(new Comparator<node>() {
public int compare(node o1, node o2) {
return o1.value-o2.value;
}});
q1.addAll(nodes);
while(!q1.isEmpty()){
node n1=q1.poll();
node n2=q1.poll();
node parent=new node(n1,n2,n1.value+n2.value);
if(q1.isEmpty()){
root=parent;return;
}
q1.add(parent);
}
}
public int getweight() {
Queue<node>q1=new ArrayDeque<node>();
q1.add(root);
int weight=0;
while (!q1.isEmpty()) {
node va=q1.poll();
if(va.left!=null){
va.left.deep=va.deep+1;va.right.deep=va.deep+1;
q1.add(va.left);q1.add(va.right);
}
else {
weight+=va.deep*va.value;
}
}
return weight;
}
public static void main(String[] args) {
List<node>list=new ArrayList<node>();
list.add(new node(2));
list.add(new node(3));
list.add(new node(6));
list.add(new node(8));list.add(new node(9));
HuffmanTree tree=new HuffmanTree();
tree.nodes=list;
tree.createTree();
System.out.println(tree.getweight());
}
} 輸出結果:
61
哈夫曼編碼
除了哈夫曼樹你聽過，哈夫曼編碼你可能也聽過，但是不一定了解它是個什麼玩意兒，哈夫曼編碼其實就是哈夫曼樹的一個非常重要的應用，在這裡就簡單介紹原理并不詳細實作了。
哈夫曼編碼定義：哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據字元出現機率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。
哈夫曼編碼的目的是為了減少存儲體積，以一個連續的字元串為例，抛開程式設計語言中實際存儲，就拿
aaaaaaaaaabbbbbcccdde
這個字元串來說，在計算機中如果每個字元都是定長存儲(假設長為4的二進制存儲)，計算機隻知道0和1的二進制，假設
a:0001
b:0010
c:0011
d:0100
e:0101
那麼上面字元串可以用二進制存儲是這樣的
000100010001000100010001……0101
如果每個字元編碼等長，那麼就沒有空間優化可言，都是單個字元長度 * 字元個數。但是如果每個字元編碼不等長，那麼設計的開放性就很強了。
比如一個字元串
aaaaabb
如果設計
a
為01，
b
設計為1。那麼二進制就為：
010101010111
如果設計
a
為1，
b
設計為01。那麼二進制就為：
111110101
如果設計
a
為1，
b
設計為0。那麼二進制就為：
1111100
你看，在計算機的01二進制世界中，明顯第二種比第一種優先，第三種又比第二種優先。是以，設計編碼要考慮讓出現多的盡量更短，出現少的稍微長點沒關系。
但是，你需要考慮的一個問題是，二進制開始0，1，01，10，11這個順序 ，如果來了001它到底是0，0，1還是0，01呢？是以編碼不等長的時候你要考慮到這個編碼要有唯一性不能出現歧義。這個怎麼搞呢？
簡單啊，計算機隻知道01二進制，而二叉樹剛好有左右兩個節點，至于一個字元它如果是對應葉子節點，那麼就可以直接确定，也就是這個數值如果映射成一個二叉樹字元不能存在非葉子節點上。
是以，哈夫曼編碼具體流程就很清晰了，先統計字元出現的次數，然後将這個次數當成權值按照上面介紹的方法構造一棵哈夫曼樹，然後樹的根不存，往左為0往右為1每個葉子節點得到的二進制數字就是它的編碼，這樣頻率高的字元在上面更短在整個二進制存儲中也更節省空間。