0.什么是哈夫曼樹？

哈夫曼樹的定義：

0.帶權(quán)路徑長度（WPL）：設(shè)二叉樹有n個葉子節(jié)點，每個葉子節(jié)點帶有權(quán)值

1.最優(yōu)二叉樹或哈夫曼樹：WPL最小的二叉樹。

2.哈夫曼樹的由來，就是為了使得平均查找次數(shù)最小而衍生出的二叉樹。

1.哈夫曼樹的構(gòu)造

0.實現(xiàn)哈夫曼樹的方式有很多種，可以使用優(yōu)先隊列（堆/Priority Queue）簡單的實現(xiàn)這個過程，給權(quán)重較低的符號較高的優(yōu)先順序，演算法如下：

0.把n個終端節(jié)點加入優(yōu)先隊列保存，則n個節(jié)點都有一個優(yōu)先權(quán)Pi，1 <= i <= n

1.如果堆中的節(jié)點數(shù)大于1，則：

<1>：從堆中移出兩個最效地Pi節(jié)點，即連續(xù)做兩次remove（min(Pi)，Priority_Queue）

<2>：產(chǎn)生一個新的節(jié)點，此節(jié)點為<1>移除節(jié)點的父節(jié)點，而此節(jié)點的權(quán)重值為<1>兩節(jié)點權(quán)重之和

<3>：把<2>中產(chǎn)生的節(jié)點加入到堆中

2.最后在堆中的點為樹的根節(jié)點 -----算法時間復(fù)雜度為：O(nlogn)

1.我們還有跟快的方式使得事件復(fù)雜度降至線性時間O(n)，就是使用兩個隊列創(chuàng)建哈夫曼樹。第一個隊列用來存儲n個符號（即n個終端節(jié)點）的權(quán)重，第二個隊列用來存儲兩兩權(quán)重的和。此方法可以保證第二個對立的前端（Front）權(quán)重永遠是最小值，方法如下：

0.把n個終端節(jié)點加入第一個隊列（按照權(quán)重的大小排列，最小的在前端，如果沒有順序則需要排序，時間復(fù)雜度就為O(nlogn)）

1.如果隊列中的節(jié)點數(shù)大于1，則：

<1>：從隊列前端移除兩個最低權(quán)重的節(jié)點

<2>：將<1>中移除的兩個節(jié)點權(quán)重相加合成一個新的節(jié)點

<3>：把新的節(jié)點加入第二個隊列

3.最后在第一個隊列的節(jié)點為根節(jié)點

使用兩個隊列，從小到大將數(shù)組a的元素加入隊列fir，隊列sec為空。每次我們將兩個元素合并，可以證明一定是三種之一。

隊列fir中的隊首和第二位合并

隊列sec中的隊首和第二位合并

隊列fir中的隊首和sec中的隊首合并優(yōu)先考慮合并的兩個數(shù)的和較小的情況。

將每次合并完的數(shù)放入sec隊列，直到sec隊列只有一個元素，結(jié)束算法。?

注意注意：雖然此方法比使用堆保存的事件復(fù)雜度還低，但是如果給出的節(jié)點并不是按照大小排好順序的，那么排序就至少花費O(nlogn)的時間。

2.哈夫曼樹的有關(guān)概念

<0>：路徑和路徑長度

在一棵樹中，從一個結(jié)點往下可以達到的孩子或?qū)O子結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。

<1>：結(jié)點的權(quán)及帶權(quán)路徑長度

若將樹中結(jié)點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。

<2>：樹的帶權(quán)路徑長度

樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和，記為WPL。

3.代碼實現(xiàn)

有點長，不過成就感杠杠的?。。?/div>