018-Huffman樹-貪心-《算法設計技巧與分析》M.H.A學習筆記
來源：程序員人生 發(fā)布時間：2016-07-28 08:43:51 閱讀次數(shù)：2480次
Huffman樹是完全2叉樹，權(quán)重較大的節(jié)點距離根較近。
Huffman編碼是1種編碼方法，該方法完全根據(jù)字符出現(xiàn)幾率來構(gòu)造異字頭的平均長度最短的碼字。
基本思路：
建立Huffman樹的進程：
假定有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。
n個權(quán)值分別設為
w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：
(1) 將w1、w2、…，wn看成是有n
棵樹的森林(每棵樹唯一1個結(jié)點)；
(2) 在森林當選出兩個根結(jié)點的權(quán)值最小的樹合并，作為1棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；
(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；
(4)重復(2)、(3)步，直到森林中只剩1棵樹為止，該樹即為所求得的哈夫曼樹。
選取權(quán)值最小的結(jié)點時我們用最小堆。
需要得出各個字母的具體編碼，我們只需要在所有的左兒子的邊標上0，右兒子的邊標上1，從根節(jié)點到目標節(jié)點的所有經(jīng)過的邊的碼就是該字母的編碼。
算法分析：
假定有n個字符。
把所有字符插入堆需要Θ(n)，從堆中刪除兩個元素和新加1個元素需要O(log n)。重復n⑴次，所以總的時間復雜度是O(n
log n)。
偽代碼：
C++代碼：
//計算哈夫曼編碼下的文本占的位數(shù)，并與定長編碼的比較。
#include<iostream>
#include<string>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<queue> //哈夫曼樹，用優(yōu)先隊列實現(xiàn)
using namespace std;
int main()
{
string s;
while (cin >> s)
{
if (s == "END") break;
int len = s.size();
int date[30] = { 0 }; //date數(shù)組記錄text中各個字符的頻數(shù)
priority_queue<int>q;
for (int i = 0; i < len; i++)
{
if (s[i] == '_') date[0]++;
else date[s[i] - 'A' + 1]++;
}
for (int i = 0; i < 27; i++)
{
if (date[i]!=0) q.push(-date[i]); //只把不同字符的頻數(shù)加入優(yōu)先隊列，字符本身與題目要求無關
} //處理使小的數(shù)據(jù)的優(yōu)先級別高
int ans = 0;
int tem;
while (!q.empty())
{
tem = -q.top(); //取出最小的兩個數(shù)，相加累計到ans中，并加入隊列，1直處理到隊列中沒有數(shù)
q.pop();
if (!q.empty())
{
tem = tem - q.top();
q.pop();
}
ans = ans + tem;
if (!q.empty())
q.push(-tem); //若隊列已沒有數(shù)據(jù)，則不添加（上面已取出最后兩個，或1個），若沒有這1步，上面whlie的判斷不成立。
}
int ans8 = len << 3;
double bi = (double)ans8 / ans;
printf("%d %d %.1lf\n", ans8, ans, bi);
}
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
