贪心算法之Huffman Code——来自Sicily

Huffman Code血与泪

/************************************************************************************************************************/ 写在前面： 因为上完体育课浑身酸痛 翘了两周的算法课 直到上周我还不以为意 但就在某个天朗气清的下午 我心血来潮打开了算法的课堂Slides 来来回回看了好多遍 但是贪心算法的例题一点都没有看懂 真的 心好痛 /************************************************************************************************************************/ Description

In computer science and information theory, a Huffman code is an optimal prefix code algorithm.

In this exercise, please use Huffman coding to encode a given data.

You should output the number of bits, denoted asB(T), to encode the data:

B(T)=∑f(c)d_T(c),

wheref(c) is the frequency of character c, and d_T(c) is be the depth of characterc's leaf in the tree T.

Input The first line is the number of characters n.

The followingn lines, each line gives the character c and its frequency f(c).

Output

 Output a single number B(T).

Sample Input Copy sample input to clipboard 5 0 5 1 4 2 6 3 2 4 3 Sample Output 45 Hint 0: 01 1: 00 2: 11 3: 100 4: 101 /***********************************************************************************************************************/ 题目分析： （1）对于给出的n组输入，进行霍夫曼编码； 获得每个character的Depth，利用公式B(T)=∑f(c)d_T(c)； 即 频数xDepth 得到输出； （2）所要解决的问题有两个：一、如何创建Huffman Tree；二、如何从Huffman Tree中得到它的Depth； （3） 通过创建优先队列（ 优先队列按照从小到大的方式进行排序 ）的方法来代替Huffman树数据结构的创建； 当优先队列中只有一个node时，结果为0； 当优先队列中node数目> 1时，进行如下操作： 每一次选择其中frequency最小的两个数相加； 创建一个新结点，并将两个数相加得到的结果push进优先队列里 直到优先队列中只有一个node为止 （4）对Huffman Tree 中Depth的求解可以采用不求得元素在HuffmanTree中的Depth来求得； 以character 3（frequency = 2）为例，它的Huffman code 为100，因此需要3x2 = 6来获得number of bits，但是可以从另外一个角度来设想，3x2=2+2+2，即将乘法转换为加法，详见代码。 /***********************************************************************************************************************/ Solution to Question one: struct HuffmanNode //创建Huffman Node的结构体，并进行初始化 { char data; int frequency; HuffmanNode *left, *right; HuffmanNode():data(0), frequency(0), left(NULL), right(NULL){} }; struct cmp //自定义比较函数 { bool operator()(HuffmanNode* a, HuffmanNode* b) { return a->frequency > b->frequency; } }; priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp>q; //创建优先队列 for(int i = 0; i < n; i++) { HuffmanNode* h = new HuffmanNode; //HuffmanNode* h = (HuffmanNde*)malloc(sizeof(HuffmanNode)); cin >> ch >> f; h->ch = ch; h->frequency = f; q.push(h); } Solution to Question two： int res=0; //frequency和 while(q.size() > 1) { HuffmanNode* temp1 = new HuffmanNode; temp1 = q.top(); q.pop(); HuffmanNode* temp2 = new HuffmanNode; temp2 = q.top(); q.pop(); HuffmanNode* temp = new HuffmanNode; temp->frequency = temp1->frequency + temp2->frequency; temp->left = temp1; temp->right = temp2; res += temp1->frequency + temp2->frequency; q.push(temp); }