用优先队列构造Huffman Tree及判断是否为最优编码的应用
前言
我们知道，要构造Huffman Tree，每次都要从堆中弹出最小的两个权重的节点，然后把这两个权重的值相加存放到新的节点中，同时让这两个节点分别成为新节点的左右儿子，再把新节点插入到堆中。假设节点个数为n，则重复n-1次后，最后堆中的那个节点就是Huffman Tree的根。
用堆实现当然可以，但是比较麻烦。你需要定义一个最小堆，堆的初始化操作，堆的插入操作，取出最小元素并调整堆的操作。先不说对这些代码是否熟悉掌握，当把这些函数都码完，别人题目都已经做完了。
这里我们用更方便的方法来构造一颗Huffman Tree。就是用STL中的优先队列。其实优先队列的本质就是一个堆。这样我们就不需要再动手码这么多的函数了。同时，如果以后的题目需要用到堆这种数据结构，直接用优先队列就可以了。
用优先队列构造Huffman Tree
要使用优先队列 priority_queue ，就需要包含头文件 #include <queue> 。
树节点的定义如下：
1 struct Data { 2 char letter; 3 int freq; 4 }; 5 6 struct TNode { 7 Data data; 8 TNode *left, *right; 9 };
然后输入字符和频率大小，把TNode*压入到优先队列中。当我们需要频率最小的频率的那个节点，只需要从优先队列中弹出一个元素就可以了，那个元素就是含有最小频率的那个节点。
不过需要注意的是，优先队列默认情况下是一个最大堆，这需要我们自定义一个比较函数，以实现最小堆。同时，我们比较的数据类型是我们自定义的数据类型TNode*，所以需要改成相应的数据类型。
这里我们通过重写仿函数，来实现最小堆：
1 class cmp { 2 public: 3 bool operator()(TNode *a, TNode *b) { 4 // 当返回true，说明a的优先级小于b 5 // 这里用 '>' 表示，如果a节点对应的频率大于b节点，就说明a的优先级小于b，从而实现堆顶元素是频率最小的那个节点，也就是最小堆 6 return a->data.freq > b->data.freq; 7 } 8 };
这里我们压入到优先队列中的数据类型是TNode*，因此在定义优先队列时，传入的数据类型是TNode*。读入数据的函数如下：
1 void readData(std::priority_queue<TNode*, std::vector<TNode*>, cmp> &pq) { // 传入在main函数中定义的优先队列 2 int n; 3 scanf("%d", &n); // 输入节点的个数 4 for (int i = 0; i < n; i++) { 5 TNode *tmp = new TNode; 6 7 getchar(); // 把多余的字符，也就是回车和空格读掉 8 scanf("%c %d", &tmp->data.letter, &tmp->data.freq); 9 tmp->left = tmp->right = NULL; 10 pq.push(tmp); // 把新节点的指针压进优先队列中 11 } 12 }
最后是核心代码，构造Huffman Tree的函数。
函数框架：如果优先队列不为空，则新建一个TNode节点，弹出堆顶的元素，并让新节点的left指向弹出这个弹出的节点。再判断一次优先队列是否为空；
- 如果不为空，就再弹出一个堆顶元素，并让新节点的right指向弹出的节点。同时，把弹出的两个节点的频率相加的结果存放到新节点中，最后把新节点的指针压到堆中。
- 如果为空，就说明刚刚弹出的节点就是我们要构造的Huffman Tree的根节点，只需要把它返回就可以了。
所以，构造Huffman Tree的函数如下：
1 TNode *createHuffmanTree(std::priority_queue<TNode*, std::vector<TNode*>, cmp> &pq) { 2 while (!pq.empty()) { // 优先队列不为空 3 TNode *tmp = new TNode; // 新建一个节点 4 tmp->left = pq.top(); // 弹出堆顶元素，作为新节点的左孩子 5 pq.pop(); 6 7 if (!pq.empty()) { // 刚才弹出元素后，优先队列不为空 8 tmp->right = pq.top(); // 再弹出一个元素，作为新节点的右孩子 9 pq.pop(); 10 11 tmp->data.freq = tmp->left->data.freq + tmp->right->data.freq; // 把左右孩子存放的频率的相加结果存放到新节点中 12 pq.push(tmp); // 把新节点的指针压入优先队列中 13 } 14 else { // 否则，刚才弹出元素后，优先队列就空了 15 return tmp->left; // 刚才弹出的元素就是Huffman Tree的根节点，直接返回即可 16 } 17 } 18 }
现在给出完整的构造Huffman Tree的代码，同时计算出这颗Huffman Tree的WPL。
1 #include <cstdio> 2 #include <queue> 3 #include <vector> 4 5 struct Data { 6 char letter; 7 int freq; 8 }; 9 10 struct TNode { 11 Data data; 12 TNode *left, *right; 13 }; 14 15 class cmp { 16 public: 17 bool operator()(TNode *a, TNode *b) { 18 return a->data.freq > b->data.freq; 19 } 20 }; 21 22 void readData(std::priority_queue<TNode*, std::vector<TNode*>, cmp> &pq); 23 TNode *createHuffmanTree(std::priority_queue<TNode*, std::vector<TNode*>, cmp> &pq); 24 int WPL(TNode *T, int depth); 25 26 int main() { 27 std::priority_queue<TNode*, std::vector<TNode*>, cmp> pq; 28 29 readData(pq); 30 TNode *huffmanTree = createHuffmanTree(pq); 31 printf("%d", WPL(huffmanTree, 0)); 32 33 return 0; 34 } 35 36 void readData(std::priority_queue<TNode*, std::vector<TNode*>, cmp> &pq) { 37 int n; 38 scanf("%d", &n); 39 for (int i = 0; i < n; i++) { 40 TNode *tmp = new TNode; 41 42 getchar(); 43 scanf("%c %d", &tmp->data.letter, &tmp->data.freq); 44 tmp->left = tmp->right = NULL; 45 pq.push(tmp); 46 } 47 } 48 49 TNode *createHuffmanTree(std::priority_queue<TNode*, std::vector<TNode*>, cmp> &pq) { 50 while (!pq.empty()) { 51 TNode *tmp = new TNode; 52 tmp->left = pq.top(); 53 pq.pop(); 54 55 if (!pq.empty()) { 56 tmp->right = pq.top(); 57 pq.pop(); 58 59 tmp->data.freq = tmp->left->data.freq + tmp->right->data.freq; 60 pq.push(tmp); 61 } 62 else { 63 return tmp->left; 64 } 65 } 66 } 67 68 int WPL(TNode *T, int depth) { 69 if (T->left == NULL && T->right == NULL) return depth * T->data.freq; 70 else return WPL(T->left, depth + 1) + WPL(T->right, depth + 1); 71 }
对应的Huffman Tree如下，通过检验WPL正是77。
满足最优编码的条件
我们知道，通过构造Huffman Tree而得到的编码一定是最优编码，但是最优编码不一定是通过构造Huffman Tree来得到的。而且通过构造Huffman Tree得到的最优编码是不唯一的，任意交换左右子树的位置得到的也是最优编码。
所以我们如何判断给定的编码是否为最优编码？首先，我们要找到最优编码的共同特点：
- 最优编码的WPL一定是最小的。
- 无歧义解码——前缀码：数据仅存于叶子节点。
- 没有度为1的节点。
其中如果满足1，2这两个条件，就一定满足第3个条件，这个可以用反证法证明。所以，要判断编码是否为最优编码，只需要检验编码是否满足1，2这两个条件就可以了。
下面给出一道具体的题目，来说明如何对编码进行1，2点的检验。
判断编码是否为最优编码
这里给出一道例题：Huffman Codes。题目就是给定一组字符的频率，再给出多组字符对应的编码，让我们来判断这些编码是否为最优编码。
原题以及更详细的题解可以参考：//www.cnblogs.com/onlyblues/p/14628257.html，这里给出多种解法，有用堆去实现的，有用优先队列实现的。
这里我们用优先队列来判断编码是否为最优编码。我们只摘取题目中的测试样例：
Sample Input:
7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11
Sample Output:
Yes
Yes
No
No
虽然题目看上去好像要构造一颗Huffman Tree，但实际上我们可以在整一个过程中不构造任何一颗树，只需要用到STL中的map和priority_queue就可以完成判断编码是否为最优编码。我们只需要判断编码是否为最优编码，因此更多的是处理频率这一数据。
先给出整一个程序框架。我们先读入字符和对应频率，同时把频率压入优先队列形成最小堆。然后再输入多组要判断是否为最优编码的数据，同时进行相应的判断和检测。所以我们的main函数的框架就是这样：
1 int main() { 2 map<char, int> letterFreq; // 用map来存储字符和对应的频率，字符映射为对应的频率 3 priority_queue< int, vector<int>, greater<int> > pq; // 优先队列，存储的数据类型为int，由于默认是最大堆，所以传入greater<int>使其变成最小堆 4 5 int n; 6 cin >> n; 7 readLetterFreq(letterFreq, pq, n); // 读入字符和频率，同时为频率生成最小堆的函数 8 checkOptimalCode(letterFreq, pq, n); // 判断多组编码是否为最优编码的函数 9 10 return 0; 11 }
下面来分析这两个函数是如何实现的。首先，对于输入的字符和对应的频率，我们用map来存储，形成一种映射的关系。同时在输入字符和频率的过程中，我们把频率压入优先队列中，这样就可以在读入字符和频率的过程中，也完成最小堆的构造。注意，我们压入优先队列的是字符频率，所以优先队列存储的数据类型是int，而不再是上面的TNode*了。
readLetterFreq函数相关代码如下：
1 void readLetterFreq(map<char, int> &letterFreq, priority_queue< int, vector<int>, greater<int> > &pq, int n) { 2 for (int i = 0; i < n; i++) { 3 char letter; 4 getchar(); // 读掉多余的字符，如回车，空格 5 cin >> letter; // 读入字符 6 getchar(); 7 cin >> letterFreq[letter]; // 读入频率，为字符的映射 8 9 pq.push(letterFreq[letter]);// 把读入的频率压入到优先队列中，构成最小堆 10 } 11 }
接下来我们要做的事情是计算给定字符的WPL。其实计算WPL不一定要构造一颗Huffman Tree，然后用深度乘以频率再求和来得到。还有一种方法是把Huffman Tree中度为2的节点存放的频率都相加起来，最后得到的结果也是WPL。这是因为叶子节点被重复计算，和用深度乘以频率的原理基本一样。就拿题目给的测试样例来举例：
这看上去还是要构造一颗树啊，但实际上，如果我们用优先队列根本不需要构造一颗树。思路是这样的：我们要有一个变量来累加如上图度为2节点存放频率。每次从优先队列里弹出两个频率，这两个频率是优先队列中所包含频率里面最小的那两个，然后把这两个频率相加，相加的结果其实就对应上图度为2节点存放的频率，也就是红色的数字。然后把相加的结果累加到一个变量，同时把相加的结果压入优先队列中。其实这个累加的过程就是累加上图红色的那些数字。一直重复，直到优先队列为空，那么那个变量最后累加的结果就是我们要计算的WPL。
计算WPL的函数代码如下：
1 int getWPL(priority_queue< int, vector<int>, greater<int> > &pq) { 2 int wpl = 0; // 用来保存累加的结果 3 while (!pq.empty()) { // 当优先队列不为空 4 int tmp = pq.top(); // 从优先队列弹出一个元素，这个元素就是最小频率 5 pq.pop(); 6 7 if (pq.empty()) break; // 如果弹出那个频元素优先队列就为空了，退出循环 8 9 tmp += pq.top(); // 如果优先队列不为空，再弹出一个元素，同时把两个频率进行相加 10 pq.pop(); 11 pq.push(tmp); // 把两个频率相加的结果压入优先队列中 12 13 wpl += tmp; // 同时，把这个相加结果进行累加，对应着累加度为2节点的存放频率 14 } 15 16 return wpl; 17 }
接下来我们需要对多组编码进行检验。即先检验编码的长度是否与给定字符频率的WPL相同，再检验是否为前缀码。
计算每组编码的方法很简单，由于输入已经给出每个字符的编码，所以就自然知道这个字符对应编码的长度。所以并不需要调用上面的getWPL函数，只需要用这个字符对应的编码长度乘以对应的频率就可以了。每一组编码的WPL计算公式为：
再判断codeLen是否与上面求出的给定频率的WPL相等，如果不相等，就说明这个编码不是最优编码，就不需要再判断是否为前缀码了。如果相等再去判断是否为前缀码。
这里还有个陷阱。首先我们要知道，一个最优编码的长度是不会超过n-1的。所以如果某个编码的长度大于n-1也说明该编码不是最优编码。
这里先给出checkOptimalCode函数的代码，接下来解释如何判断编码是否为前缀码。
1 void checkOptimalCode(map<char, int> &letterFreq, priority_queue< int, vector<int>, greater<int> > &pq, int n) { 2 int wpl = getWPL(pq); // 用不构造Huffman Tree的方法来计算WPL 3 4 int m; 5 cin >> m; // 输入判断编码的组数m 6 for (int i = 0; i < m; i++) { 7 string code[n]; 8 int codeLen = 0; 9 bool ret = true; 10 11 for (int i = 0; i < n; i++) { 12 char letter; 13 getchar(); 14 cin >> letter >> code[i]; // 读入字符和对应的编码 15 16 if (ret) { // 如果已经知道该组编码不是最优编码就不需要再计算编码长度了，但仍要继续输入 17 if (code[i].size() > n - 1) ret = false; // 如果某个字符的编码长度大于n-1，说明该组编码不是最优编码 18 codeLen += code[i].size() * letterFreq[letter]; // 计算编码长度 19 } 20 } 21 22 if (ret && codeLen == wpl) { // 如果ret == true并且编码长度与WPL相同，才判断该组编码是否为前缀码 23 for (int i = 0; i < n; i++) { // 每个字符都跟它之后的字符进行判断是否满足前缀码的要求 24 for (int j = i + 1; j < n; j++) { 25 // 判断某个编码是否与另外一个编码前m个位置的相同，详细请看图片 26 if (code[i].substr(0, code[j].size()) == code[j].substr(0, code[i].size())) { 27 ret = false; // 只要有一对编码的前缀相同，就说明这组的编码不满足前缀码 28 break; // 后面的字符不需要判断了，直接退出退出判断前缀码的循环 29 } 30 } 31 if (ret == false) break; 32 } 33 } 34 else { 35 ret = false; 36 } 37 38 cout << (ret ? "Yes\n" : "No\n"); 39 } 40 }
下面来说说如何判断编码是否为前缀码。首先，假设现在有两个编码，如果这两个编码不满足前缀码的话，比如”110″和”1101″，那么其中一个编码会与另外一个编码前的m个位置的相同（其中m是指这两个编码长度中最小的那个长度）。也就是说”110″，与”1101″的前3个位置的”110″相同，就说明”110″和”1101″不满足前缀码。
我们需要对同组编码的每两个字符进行比较，需要比较的次数为 C(n, 2) = n * (n – 1) / 2 。
相关的函数代码上面已经给出。主要是 code[i].substr(0, code[j].size()) == code[j].substr(0, code[i].size()) 这个部分。
code[i].substr(0, code[j].size()) == code[j].substr(0, code[i].size()) ，这么做始终能够保证取到两个编码中，长度最小那个编码的全部，以及另外一个编码的前面同样长度的部分，来进行判断是否满足前缀码。
下面给出这道题完整的AC代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 #include <queue> 6 #include <map> 7 using namespace std; 8 9 void readLetterFreq(map<char, int> &letterFreq, priority_queue< int, vector<int>, greater<int> > &pq, int n); 10 void checkOptimalCode(map<char, int> &letterFreq, priority_queue< int, vector<int>, greater<int> > &pq, int n); 11 int getWPL(priority_queue< int, vector<int>, greater<int> > &pq); 12 13 int main() { 14 map<char, int> letterFreq; 15 priority_queue< int, vector<int>, greater<int> > pq; 16 17 int n; 18 cin >> n; 19 readLetterFreq(letterFreq, pq, n); 20 checkOptimalCode(letterFreq, pq, n); 21 22 return 0; 23 } 24 25 void readLetterFreq(map<char, int> &letterFreq, priority_queue< int, vector<int>, greater<int> > &pq, int n) { 26 for (int i = 0; i < n; i++) { 27 char letter; 28 getchar(); 29 cin >> letter; 30 getchar(); 31 cin >> letterFreq[letter]; 32 33 pq.push(letterFreq[letter]); 34 } 35 } 36 37 void checkOptimalCode(map<char, int> &letterFreq, priority_queue< int, vector<int>, greater<int> > &pq, int n) { 38 int wpl = getWPL(pq); 39 40 int m; 41 cin >> m; 42 for (int i = 0; i < m; i++) { 43 string code[n]; 44 int codeLen = 0; 45 bool ret = true; 46 47 for (int i = 0; i < n; i++) { 48 char letter; 49 getchar(); 50 cin >> letter >> code[i]; 51 52 if (ret) { 53 if (code[i].size() > n - 1) ret = false; 54 codeLen += code[i].size() * letterFreq[letter]; 55 } 56 } 57 58 if (ret && codeLen == wpl) { 59 for (int i = 0; i < n; i++) { 60 for (int j = i + 1; j < n; j++) { 61 if (code[i].substr(0, code[j].size()) == code[j].substr(0, code[i].size())) { 62 ret = false; 63 break; 64 } 65 } 66 if (ret == false) break; 67 } 68 } 69 else { 70 ret = false; 71 } 72 73 cout << (ret ? "Yes\n" : "No\n"); 74 } 75 } 76 77 int getWPL(priority_queue< int, vector<int>, greater<int> > &pq) { 78 int wpl = 0; 79 while (!pq.empty()) { 80 int tmp = pq.top(); 81 pq.pop(); 82 83 if (pq.empty()) break; 84 85 tmp += pq.top(); 86 pq.pop(); 87 pq.push(tmp); 88 89 wpl += tmp; 90 } 91 92 return wpl; 93 }
参考资料
Huffman Codes：//www.cnblogs.com/onlyblues/p/14628257.html
priority_queue的用法：//www.cnblogs.com/Deribs4/p/5657746.html
