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