In 1953, David A. Huffman published his paper "A Method for the Construction of Minimum-Redundancy Codes", and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters 'a', 'x', 'u' and 'z' are 4, 2, 1 and 1, respectively. We may either encode the symbols as {'a'=0, 'x'=10, 'u'=110, 'z'=111}, or in another way as {'a'=1, 'x'=01, 'u'=001, 'z'=000}, both compress the string into 14 bits. Another set of code can be given as {'a'=0, 'x'=11, 'u'=100, 'z'=101}, but {'a'=0, 'x'=01, 'u'=011, 'z'=001} is NOT correct since "aaaxuaxz" and "aazuaxax" can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.html
Each input file contains one test case. For each case, the first line gives an integer N (2), then followed by a line that contains all the N distinct characters and their frequencies in the following format:ios
c[1] f[1] c[2] f[2] ... c[N] f[N]数据结构
where c[i]
is a character chosen from {'0' - '9', 'a' - 'z', 'A' - 'Z', '_'}, and f[i]
is the frequency of c[i]
and is an integer no more than 1000. The next line gives a positive integer M (≤), then followed by M student submissions. Each student submission consists of N lines, each in the format:ide
c[i] code[i]函数
where c[i]
is the i
-th character and code[i]
is an non-empty string of no more than 63 '0's and '1's.测试
For each test case, print in each line either "Yes" if the student's submission is correct, or "No" if not.编码
Note: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code length being optimal is considered correct.spa
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 113d
Yes
Yes
No
No指针
要判断编码是否为最优编码,须要对编码进行两个方面的检验:对每一组编码来判断WPL是否为最小的,以及是否为前缀码。
下面给出第一种思路,须要构建Huffman Tree的方法,同时也是用堆来实现的。
树节点的定义以下:
1 struct Data { 2 char letter; 3 int freq; 4 }; 5 6 struct TNode { 7 Data data; 8 TNode *left, *right; 9 };
首先咱们要根据给出的字符频率来构造出一颗对应的Huffman Tree,同时计算出WPL。
又由于咱们是用堆来实现的,因此要构造一颗Huffman Tree咱们先要把给定的频率来构建一个最小堆。
这里咱们须要对堆进行定义,同时还要定义堆的相关操做。这里就直接上代码,不解释了。
1 struct Heap { 2 TNode *H; // 堆的每个元素的数据类型是树节点TNode 3 int size; 4 int capacity; 5 }; 6 7 Heap *createMinHeap(int n) { 8 Heap *minHeap = new Heap; 9 minHeap->size = 0; 10 minHeap->capacity = n; 11 minHeap->H = new TNode[n + 1]; 12 minHeap->H[0].data.freq = -1; 13 14 for (int i = 0; i < minHeap->capacity; i++) { 15 TNode *tmp = new TNode; 16 tmp->left = tmp->right = NULL; 17 getchar(); 18 scanf("%c %d", &tmp->data.letter, &tmp->data.freq); 19 insertHeap(minHeap, tmp); 20 } 21 22 return minHeap; 23 } 24 25 void insertHeap(Heap *minHeap, TNode *treeNode) { 26 int pos = ++minHeap->size; 27 for ( ; treeNode->data.freq < minHeap->H[pos / 2].data.freq; pos /= 2) { 28 minHeap->H[pos] = minHeap->H[pos / 2]; 29 } 30 minHeap->H[pos] = *treeNode; 31 } 32 33 TNode *deleteMin(Heap *minHeap) { 34 TNode *minTreeNode = new TNode; 35 *minTreeNode = minHeap->H[1]; 36 TNode tmp = minHeap->H[minHeap->size--]; 37 38 int parent = 1, child; 39 for ( ; parent * 2 <= minHeap->size; parent = child) { 40 child = parent * 2; 41 if (child != minHeap->size && minHeap->H[child].data.freq > minHeap->H[child + 1].data.freq) child++; 42 if (tmp.data.freq < minHeap->H[child].data.freq) break; 43 else minHeap->H[parent] = minHeap->H[child]; 44 } 45 minHeap->H[parent] = tmp; 46 47 return minTreeNode; 48 }
构建好最小堆后,下一步咱们须要经过这个堆来构造出对应的Huffman Tree。
就是每次从堆中弹出最小频率的那两个节点,而后把这两个节点分别插在新节点的左右边,做为左右孩子。再把新节点压入堆中。如此循环n-1次后(其中n表明节点的个数),堆中就只剩下一个元素,那个元素就是Huffman Tree的根节点,咱们直接返回便可。
按照上面构造Huffman Tree的思路,相应的代码以下:
1 TNode *createHuffmanTree(Heap *minHeap) { 2 int n = minHeap->size - 1; 3 while (n--) { 4 TNode *tmp = new TNode; 5 tmp->left = deleteMin(minHeap); 6 tmp->right = deleteMin(minHeap); 7 tmp->data.freq = tmp->left->data.freq + tmp->right->data.freq; 8 9 insertHeap(minHeap, tmp); 10 } 11 12 return deleteMin(minHeap); 13 }
而后,咱们要根据这颗Huffman Tree来计算WPL。咱们用递归来实现计算WPL。
若是这个节点是叶子节点,那么就用当前深度乘以对应的频率,而后返回。若是不是叶子节点,就递归来计算左右子树的WPL,相加后返回。
1 int WPL(TNode *T, int depth) { 2 if (T->left == NULL && T->right == NULL) return depth * T->data.freq; // 叶子节点直接返回结果 3 else return WPL(T->left, depth + 1) + WPL(T->right, depth + 1); // 不是叶子节点,计算左右子树的WPL并返回,同时因为左右子树的深度加深一层,记得depth+1 4 }
好了,折腾了这么久,终于计算出给定频率的WPL了。
接下来咱们先对每一组编码来检测其WPL是否是最小的,也就是每组编码的WPL是否与给定频率的WPL相等。
计算方法很简单,每一组编码的WPL计算公式为:
再判断codeLen是否与上面求出的给定频率的WPL相等,若是不相等,就说明这个编码不是最优编码,就不须要再判断是否为前缀码了。若是相等再去判断是否为前缀码。
这里还有个陷阱。首先咱们要知道,一个最优编码的长度是不会超过n-1的。因此若是某个编码的长度大于n-1也说明该编码不是最优编码。
这里同时给出计算编码长度和判断是不是前缀码的函数:
1 bool check(TNode *huffmanTree, int n) { 2 int wpl = WPL(huffmanTree, 0); // 计算给定频率构成的Huuffman Tree的WPL 3 4 std::string code[n]; // 存放每个字符的编码 5 int codeLen = 0; 6 bool ret = true; // 用来标记该组编码是否为最优编码 7 8 for (int i = 0; i < n; i++) { 9 char letter; 10 getchar(); 11 scanf("%c", &letter); 12 getchar(); 13 std::cin >> code[i]; 14 15 if (ret) { // 若是已经知道该组编码不是最优编码就不须要再计算编码长度了,但仍要继续输入 16 if (code[i].size() > n - 1) ret = false; // 若是某个字符的编码长度大于n-1,说明该组编码不是最优编码 17 codeLen += code[i].size() * findFreq(huffmanTree, letter); // 计算编码长度 18 } 19 } 20 21 if (ret && codeLen == wpl) { // 若是ret == true而且编码长度与WPL相同,接着判断该组编码是否为前缀码 22 TNode *T = new TNode; // 为这组编码构造一颗Huffman Tree,初始化Huffman Tree的根节点 23 T->data.freq = 0; 24 T->left = T->right = NULL; 25 26 for (int i = 0; i < n; i++) { // 有n个节点,须要判断n次 27 TNode *pre = T; // 每次判断一个字符都从根节点开始 28 29 for (std::string::iterator it = code[i].begin(); it != code[i].end(); it++) { // 对该字符的每个编码进行判断 30 if (*it == '0') { // 若是编码是0 31 if (pre->left == NULL) { // 若是当前节点的左子树为空 32 TNode *tmp = new TNode; // 就为当前节点生成一颗左子树 33 tmp->data.freq = 0; // 该节点的频率标记为0,表示该节点尚未字符占用 34 tmp->left = tmp->right = NULL; 35 pre->left = tmp; 36 } 37 pre = pre->left; // pre指针指向左子树 38 } 39 else { // 若是编码是1 40 if (pre->right == NULL) { // 若是当前节点的右子树为空 41 TNode *tmp = new TNode; // 就为当前节点生成一颗右子树 42 tmp->data.freq = 0; // 该节点的频率标记为0,表示该节点尚未字符占用 43 tmp->left = tmp->right = NULL; 44 pre->right = tmp; 45 } 46 pre = pre->right; // pre指针指向左子树 47 } 48 } 49 50 // 读完了字符的编码后,pre指针就指向这个字符应该占用的位置 51 // 这时须要判断pre指向的这个节点是否为叶子节点,而且该节点有没有被其余字符占用 52 if (pre->left == NULL && pre->right == NULL && pre->data.freq == 0) { 53 pre->data.freq = 1; // 若是是叶子节点而且没有被占用,该字符就占用了这个节点,并把这个节点的频率标记为1 54 } 55 else { // 不然,若是这些条件中有一个不知足 56 ret = false; // 就说明该组字符不知足前缀码的要求,ret赋值为false 57 break; // 后面的字符不须要判断了,直接退出退出判断前缀码的循环 58 } 59 } 60 } 61 else { // 若是ret == false而且编码长度不等于WPL,就说明该组编码不是最优编码 62 ret = false; 63 } 64 65 return ret; 66 }
这里是经过构造一颗Huffman Tree来判断该组编码是否符合前缀码。
判断的过程以下:
有一个指向Huffman Tree根节点的指针。
读完该字符的编码后,那么此时字符应该放入这个指针指向的节点。这个节点要知足两个条件才能够放入:
若是有一个条件不知足,就说明该组编码不是前缀码。
最后,给出这种方法的完整AC代码,代码量有点多。
#include <cstdio> #include <iostream> #include <string> struct Data { char letter; int freq; }; struct TNode { Data data; TNode *left, *right; }; struct Heap { TNode *H; int size; int capacity; }; Heap *createMinHeap(int n); void insertHeap(Heap *minHeap, TNode *treeNode); TNode *deleteHeap(Heap *minHeap); TNode *createHuffmanTree(Heap *minHeap); bool check(TNode *huffmanTree, int n); int WPL(TNode *T, int depth); int findFreq(TNode *huffmanTree, char letter); int main() { int n; scanf("%d", &n); Heap *minHeap = createMinHeap(n); TNode *huffmanTree = createHuffmanTree(minHeap); int m; scanf("%d", &m); for (int i = 0; i < m; i++) { bool ret = check(huffmanTree, n); printf("%s\n", ret ? "Yes" : "No"); } return 0; } Heap *createMinHeap(int n) { Heap *minHeap = new Heap; minHeap->size = 0; minHeap->capacity = n; minHeap->H = new TNode[n + 1]; minHeap->H[0].data.freq = -1; for (int i = 0; i < minHeap->capacity; i++) { TNode *tmp = new TNode; tmp->left = tmp->right = NULL; getchar(); scanf("%c %d", &tmp->data.letter, &tmp->data.freq); insertHeap(minHeap, tmp); } return minHeap; } void insertHeap(Heap *minHeap, TNode *treeNode) { int pos = ++minHeap->size; for ( ; treeNode->data.freq < minHeap->H[pos / 2].data.freq; pos /= 2) { minHeap->H[pos] = minHeap->H[pos / 2]; } minHeap->H[pos] = *treeNode; } TNode *deleteHeap(Heap *minHeap) { TNode *minTreeNode = new TNode; *minTreeNode = minHeap->H[1]; TNode tmp = minHeap->H[minHeap->size--]; int parent = 1, child; for ( ; parent * 2 <= minHeap->size; parent = child) { child = parent * 2; if (child != minHeap->size && minHeap->H[child].data.freq > minHeap->H[child + 1].data.freq) child++; if (tmp.data.freq < minHeap->H[child].data.freq) break; else minHeap->H[parent] = minHeap->H[child]; } minHeap->H[parent] = tmp; return minTreeNode; } TNode *createHuffmanTree(Heap *minHeap) { int n = minHeap->size - 1; while (n--) { TNode *tmp = new TNode; tmp->left = deleteHeap(minHeap); tmp->right = deleteHeap(minHeap); tmp->data.freq = tmp->left->data.freq + tmp->right->data.freq; insertHeap(minHeap, tmp); } return deleteHeap(minHeap); } bool check(TNode *huffmanTree, int n) { int wpl = WPL(huffmanTree, 0); std::string code[n]; int codeLen = 0; bool ret = true; for (int i = 0; i < n; i++) { char letter; getchar(); scanf("%c", &letter); getchar(); std::cin >> code[i]; if (ret) { if (code[i].size() > n - 1) ret = false; codeLen += code[i].size() * findFreq(huffmanTree, letter); } } if (ret && codeLen == wpl) { TNode *T = new TNode; T->data.freq = 0; T->left = T->right = NULL; for (int i = 0; i < n; i++) { TNode *pre = T; for (std::string::iterator it = code[i].begin(); it != code[i].end(); it++) { if (*it == '0') { if (pre->left == NULL) { TNode *tmp = new TNode; tmp->data.freq = 0; tmp->left = tmp->right = NULL; pre->left = tmp; } pre = pre->left; } else { if (pre->right == NULL) { TNode *tmp = new TNode; tmp->data.freq = 0; tmp->left = tmp->right = NULL; pre->right = tmp; } pre = pre->right; } } if (pre->left == NULL && pre->right == NULL && pre->data.freq == 0) { pre->data.freq = 1; } else { ret = false; break; } } } else { ret = false; } return ret; } int WPL(TNode *T, int depth) { if (T->left == NULL && T->right == NULL) return depth * T->data.freq; else return WPL(T->left, depth + 1) + WPL(T->right, depth + 1); } int findFreq(TNode *huffmanTree, char letter) { int ret = 0; if (huffmanTree) { if (huffmanTree->left == NULL && huffmanTree->right == NULL && huffmanTree->data.letter == letter) ret = huffmanTree->data.freq; if (ret == 0) ret = findFreq(huffmanTree->left, letter); if (ret == 0) ret = findFreq(huffmanTree->right, letter); } return ret; }
而后,咱们来对断定前缀码的代码进行改进,下面给出断定前缀码的另一种思路,这个方法不须要构造Huffman Tree。
首先,假设如今有两个编码,若是这两个编码不知足前缀码的话,好比"110"和"1101",那么其中一个编码会与另一个编码前的m个位置的相同(其中m是指这两个编码长度中最小的那个长度)。也就是说"110",与"1101"的前3个位置的"110"相同,就说明"110"和"1101"不知足前缀码。
咱们须要对同组编码的每两个字符进行比较,须要比较的次数为 C(n, 2) = n * (n - 1) / 2 。
check函数改进的代码以下:
1 bool check(TNode *huffmanTree, int n) { 2 int wpl = WPL(huffmanTree, 0); 3 4 std::string code[n]; 5 int codeLen = 0; 6 bool ret = true; 7 8 for (int i = 0; i < n; i++) { 9 char letter; 10 getchar(); 11 scanf("%c", &letter); 12 getchar(); 13 std::cin >> code[i]; 14 15 if (ret) { 16 if (code[i].size() > n - 1) ret = false; 17 codeLen += code[i].size() * findFreq(huffmanTree, letter); 18 } 19 } 20 21 if (ret && codeLen == wpl) { // 同样的,若是ret == true而且编码长度与WPL相同,才判断该组编码是否为前缀码 22 for (int i = 0; i < n; i++) { // 每一个字符都跟它以后的字符进行判断是否知足前缀码的要求 23 for (int j = i + 1; j < n; j++) { 24 // 判断某个编码是否与另一个编码前m个位置的相同,详细请看图片 25 if (code[i].substr(0, code[j].size()) == code[j].substr(0, code[i].size())) { 26 ret = false; // 只要有一对编码的前缀相同,就说明这组的编码不知足前缀码 27 break; // 后面的字符不须要判断了,直接退出退出判断前缀码的循环 28 } 29 } 30 if (ret == false) break; 31 } 32 } 33 else { 34 ret = false; 35 } 36 37 return ret; 38 }
code[i].substr(0, code[j].size()) == code[j].substr(0, code[i].size()) ,这么作始终可以保证取到两个编码中,长度最小那个编码的所有,以及另一个编码的前面一样长度的部分,来进行判断是否知足前缀码。
这个方法也能够经过,下面给出完整的AC代码,其中改动的部分就是check部分,其余的不变。
#include <cstdio> #include <iostream> #include <string> struct Data { char letter; int freq; }; struct TNode { Data data; TNode *left, *right; }; struct Heap { TNode *H; int size; int capacity; }; Heap *createMinHeap(int n); void insertHeap(Heap *minHeap, TNode *treeNode); TNode *deleteHeap(Heap *minHeap); TNode *createHuffmanTree(Heap *minHeap); bool check(TNode *huffmanTree, int n); int WPL(TNode *T, int depth); int findFreq(TNode *huffmanTree, char letter); int main() { int n; scanf("%d", &n); Heap *minHeap = createMinHeap(n); TNode *huffmanTree = createHuffmanTree(minHeap); int m; scanf("%d", &m); for (int i = 0; i < m; i++) { bool ret = check(huffmanTree, n); printf("%s\n", ret ? "Yes" : "No"); } return 0; } Heap *createMinHeap(int n) { Heap *minHeap = new Heap; minHeap->size = 0; minHeap->capacity = n; minHeap->H = new TNode[n + 1]; minHeap->H[0].data.freq = -1; for (int i = 0; i < minHeap->capacity; i++) { TNode *tmp = new TNode; tmp->left = tmp->right = NULL; getchar(); scanf("%c %d", &tmp->data.letter, &tmp->data.freq); insertHeap(minHeap, tmp); } return minHeap; } void insertHeap(Heap *minHeap, TNode *treeNode) { int pos = ++minHeap->size; for ( ; treeNode->data.freq < minHeap->H[pos / 2].data.freq; pos /= 2) { minHeap->H[pos] = minHeap->H[pos / 2]; } minHeap->H[pos] = *treeNode; } TNode *deleteHeap(Heap *minHeap) { TNode *minTreeNode = new TNode; *minTreeNode = minHeap->H[1]; TNode tmp = minHeap->H[minHeap->size--]; int parent = 1, child; for ( ; parent * 2 <= minHeap->size; parent = child) { child = parent * 2; if (child != minHeap->size && minHeap->H[child].data.freq > minHeap->H[child + 1].data.freq) child++; if (tmp.data.freq < minHeap->H[child].data.freq) break; else minHeap->H[parent] = minHeap->H[child]; } minHeap->H[parent] = tmp; return minTreeNode; } TNode *createHuffmanTree(Heap *minHeap) { int n = minHeap->size - 1; while (n--) { TNode *tmp = new TNode; tmp->left = deleteHeap(minHeap); tmp->right = deleteHeap(minHeap); tmp->data.freq = tmp->left->data.freq + tmp->right->data.freq; insertHeap(minHeap, tmp); } return deleteHeap(minHeap); } bool check(TNode *huffmanTree, int n) { int wpl = WPL(huffmanTree, 0); std::string code[n]; int codeLen = 0; bool ret = true; for (int i = 0; i < n; i++) { char letter; getchar(); scanf("%c", &letter); getchar(); std::cin >> code[i]; if (ret) { if (code[i].size() > n - 1) ret = false; codeLen += code[i].size() * findFreq(huffmanTree, letter); } } if (ret && codeLen == wpl) { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (code[i].substr(0, code[j].size()) == code[j].substr(0, code[i].size())) { ret = false; break; } } if (ret == false) break; } } else { ret = false; } return ret; } int WPL(TNode *T, int depth) { if (T->left == NULL && T->right == NULL) return depth * T->data.freq; else return WPL(T->left, depth + 1) + WPL(T->right, depth + 1); } int findFreq(TNode *huffmanTree, char letter) { int ret = 0; if (huffmanTree) { if (huffmanTree->left == NULL && huffmanTree->right == NULL && huffmanTree->data.letter == letter) ret = huffmanTree->data.freq; if (ret == 0) ret = findFreq(huffmanTree->left, letter); if (ret == 0) ret = findFreq(huffmanTree->right, letter); } return ret; }
还能够再改进!咱们不用堆,而改用优先队列,同时不须要构造任何的Huffman Tree,甚至不须要定义树节点,也能够计算出给定频率的WPL!而且代码长度也缩短许多。
这里主要说明如何经过不构造Huffman Tree来计算给定频率的WPL。其实计算WPL不必定要用深度乘以频率再求和来获得。另一种方法是把Huffman Tree中度为2的节点存放的频率都相加起来,最后获得的结果也是WPL。这是由于叶子节点被重复计算,和用深度乘以频率的原理基本同样。
就拿题目给的测试样例来举例:
咱们往优先队列里面压的就是每一个字符对应的频率,而不是树节点。代码实现的过程是:咱们要有一个变量来累加如上图度为2节点存放频率。每次从优先队列里弹出两个频率,这两个频率是优先队列中所包含频率里面最小的那两个,而后把这两个频率相加,相加的结果其实就对应上图度为2节点存放的频率,也就是红色的数字。而后把相加的结果累加到那个变量,同时把相加的结果压入优先队列中。其实这个累加的过程就是累加上图红色的那些数字。一直重复,直到优先队列为空,那么那个变量最后累加的结果就是咱们要计算的WPL。
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; // 用map来存储字符和对应的频率,字符映射为对应的频率 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); // 用不构造Huffman Tree的方法来计算WPL 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; // 同时,把这个相加结果进行累加,对应着累加度为2节点存放的频率 90 } 91 92 return wpl; 93 }
浙江大学——数据结构:https://www.icourse163.org/course/ZJU-93001?tid=1461682474
priority_queue的用法:https://www.cnblogs.com/Deribs4/p/5657746.html
pta5-9 Huffman Codes (30分):https://www.cnblogs.com/Deribs4/p/4801656.html