本文將通過 Huffman 編碼樹的構(gòu)造問題扮授，介紹優(yōu)先隊(duì)列結(jié)構(gòu)的具體應(yīng)用傅寡。
二進(jìn)制編碼
通訊系統(tǒng)可以幫助人們將一段信息從發(fā)送端傳送給接收端舵匾。最常見的信息形式是字符串诡曙，即由來自某一有限字符集Σ 的若干個(gè)字符組成的一個(gè)序列M = (x1, …, xn)，xi∈Σ笆豁，1≤i≤n郎汪。在將M 加載至信道上并發(fā)送之前，首先需要對(duì)M 進(jìn)行編碼（Encoding）闯狱。通常采用的都是二進(jìn)制編碼煞赢，以英文字母集Σ = {A, B, C, …, Z}為例，若需要傳送字符串“MAIN”哄孤，一種可行的編碼方式就是：
e('N') = "00"
e('A') = "010"
e('I') = "011"
e('M') = "1"
若令每個(gè)字符分別對(duì)應(yīng)于一匹葉子照筑，則從根節(jié)點(diǎn)通往每匹葉子的路徑，就對(duì)應(yīng)于相應(yīng)字符的二進(jìn)制編碼瘦陈，這樣的一棵樹也稱作二叉編碼樹凝危。
二進(jìn)制解碼
反過來，根據(jù)這棵編碼樹也可以便捷地完成解碼工作晨逝。
從頭開始掃描接收到的二進(jìn)制信息流蛾默；
從根節(jié)點(diǎn)開始，根據(jù)各比特位不斷進(jìn)入下一層節(jié)點(diǎn)捉貌；
到達(dá)葉子節(jié)點(diǎn)后支鸡，輸出其對(duì)應(yīng)的字符冬念；
然后重新回到根節(jié)點(diǎn)，并繼續(xù)掃描二進(jìn)制流牧挣。
實(shí)際上刘急，這一過程可以在接收過程中實(shí)時(shí)進(jìn)行，而不必等到所有的比特位都到達(dá)之后才開始解碼浸踩。
最優(yōu)編碼樹
在實(shí)際的通訊系統(tǒng)中叔汁，信道的使用效率是個(gè)很重要的問題，這在很大程度上取決于編碼算法本身的效率检碗。很自然地据块，我們當(dāng)然希望能夠用盡可能少的比特位來表示字符串。那么折剃，如何做到這一點(diǎn)呢另假？在什么情況下能夠做到這一點(diǎn)呢？
先介紹一項(xiàng)編碼效率的重要指標(biāo)——平均編碼長度
在二叉編碼樹中每個(gè)字符 c 的編碼長度為對(duì)應(yīng)的葉子的深度 depth(c)怕犁。
Σ 中各字符的編碼長度總和除以字符集 Σ 就是單個(gè)字符的平均編碼長度边篮。
對(duì)于任一字符集Σ，若在所有的編碼方式中奏甫，某一編碼方式 e() 使得平均編碼長度最短戈轿，則稱 e() 為 Σ 的一種最優(yōu)編碼，與之對(duì)應(yīng)的編碼樹稱作 Σ 的一棵最優(yōu)編碼樹阵子。
我們注意到思杯，對(duì)于同一字符集Σ，所有深度不超過|Σ|的編碼樹只有有限棵挠进，因此其中的總編碼長度最小者必然存在（盡管不見得唯一）色乾。
如何找到最優(yōu)編碼樹
首先需要更加深入地了解最優(yōu)編碼樹的性質(zhì)，在最優(yōu)二叉編碼樹中：
(1) 每個(gè)內(nèi)部節(jié)點(diǎn)的度數(shù)均為 2
(2) 各葉子之間的深度差不超過 1
推論：基于由 2 | Σ | -1 個(gè)節(jié)點(diǎn)構(gòu)成的完全二叉樹 T领突，將 Σ 中的字符任意分配給 T 的 | Σ | 匹葉子暖璧，即可得到 Σ 的一棵最優(yōu)編碼樹。
這一推論也直接給出了一個(gè)構(gòu)造最優(yōu)編碼樹的算法君旦。
帶權(quán)編碼
上面所介紹的最優(yōu)編碼樹澎办，在實(shí)際應(yīng)用中的利用價(jià)值并不大。不難看出于宙，只有當(dāng) Σ 中各個(gè)字符在信息串中出現(xiàn)的概率相等時(shí)浮驳，其最優(yōu)性才有意義悍汛，遺憾的是捞魁，這一條件很難滿足。
在實(shí)際應(yīng)用中离咐，Σ 中各字符的出現(xiàn)頻率不僅很少相等或相近谱俭，而且往往相差懸殊奉件。以英文信息串為例，'e'昆著、't'等字符的出現(xiàn)頻率通常都是'z'县貌、'j'等字符的數(shù)百倍。在這種情況下凑懂，就應(yīng)該從另一角度衡量每個(gè)字符的編碼長度煤痕。
若假設(shè)字符 c 出現(xiàn)的概率為 p(c) ≥ 0， 其在二叉編碼樹中對(duì)應(yīng)的葉子的深度記作depth(c)接谨，則：
- 每個(gè)字符 c∈Σ 的帶權(quán)編碼長度為|e(c)| = depth(c) × p(c)
- 對(duì)于任一字符集 Σ 的任一編碼方式 e()摆碉，Σ 中各字符的平均帶權(quán)編碼長度總和|e(c)|稱作 e()（或其對(duì)應(yīng)的二叉編碼樹）的平均帶權(quán)編碼長度。
例如：信息串" M A M A N I "
各字符出現(xiàn)的概率分別為p('M') = 2/6脓豪、p('A') = 2/6巷帝、p('I') = 1/6 和p('N') = 1/6
則各字符的帶權(quán)編碼長度分別為：
|e('M')| = 3×(2/6) = 1
|e('A')| = 3×(2/6) = 1
|e('I')| = 2×(1/6) = 1/3
|e('N')| = 1×(1/6) = 1/6
相應(yīng)地，這一編碼方式對(duì)應(yīng)的平均帶權(quán)編碼長度就是：
|e('M')| + |e('A')| + |e('I')| + |e('N')| = 2.5
如何找到最優(yōu)帶權(quán)編碼樹（不唯一）
首先
** 完全二叉編碼樹 ≠ 平均帶權(quán)編碼最短 **
最優(yōu)帶權(quán)編碼樹有以下性質(zhì)：
在最優(yōu)帶權(quán)編碼樹中扫夜，內(nèi)部節(jié)點(diǎn)的度數(shù)均為 2
對(duì)于字符出現(xiàn)概率為 p()的任一字符集 Σ 楞泼，若字符 x 和 y 在所有字符中的出現(xiàn)概率最低，則必然存在某棵最優(yōu)帶權(quán)編碼樹笤闯，使得 x 和 y 在其中同處于最底層堕阔，而且互為兄弟。
對(duì)于字符出現(xiàn)概率滿足一定分布的任一字符集 Σ 颗味，我們都可以按照如下算法來構(gòu)造其對(duì)應(yīng)的 Huffman 編碼樹：
首先印蔬，對(duì)應(yīng)于 Σ 中的每一字符，分別建立一棵由單個(gè)節(jié)點(diǎn)組成樹脱衙，其權(quán)重就是該字符出現(xiàn)的頻率侥猬，這|Σ |棵樹組成一個(gè)森林 F。
接下來捐韩，從 F 中選出權(quán)重最小的兩棵樹退唠，創(chuàng)建一個(gè)新節(jié)點(diǎn)，并分別以這兩棵樹作為其左荤胁、右子樹瞧预，從而將它們合成為一棵更高的樹，其權(quán)重等于其左仅政、右子樹權(quán)重之和垢油。
這一選取、合并的過程將反復(fù)進(jìn)行圆丹，直到最后 F 中只剩下一棵樹??它就是我們所需要的 Huffman 編碼樹滩愁。
舉個(gè)例子：
| 字符 | 出現(xiàn)頻率 |
|---|---|
| A | 623 |
| B | 99 |
| C | 239 |
| D | 290 |
| E | 906 |
| F | 224 |
基于優(yōu)先隊(duì)列的 Huffman 樹構(gòu)造算法
具體方法是：
1，始終將森林中的所有樹（根）組織為一個(gè)優(yōu)先隊(duì)列辫封，比如基于二叉堆實(shí)現(xiàn)的優(yōu)先隊(duì)列硝枉。
2廉丽，這樣，只要連續(xù)地調(diào)用 delMin()方法兩次妻味，就可以找出當(dāng)前權(quán)重最小的兩棵樹正压。
3，在將這兩棵樹合并為一棵新樹之后责球，可以調(diào)用 insert()方法將其重新插入優(yōu)先隊(duì)列焦履。
4，這一過程將反復(fù)進(jìn)行雏逾，每迭代一次裁良，森林的規(guī)模就會(huì)減小 1。
因此校套，經(jīng)過 n-1 次迭代价脾，森林中將只包含一棵樹，即 Huffman 編碼樹笛匙。
