C++使用优先队列来构建huffman树[哈夫曼树]

C++使用优先队列来构建huffman树[哈夫曼树]

1. #include <iostream>   
2. #include <queue>   
3. #include <string.h>   
4. #include <vector>   
5. #include <algorithm>   
6. using namespace std;  
7.   
8. char Table[26];  
9.   
10. struct Node  
11. {  
12.     int     freq;  
13.     char    val;  
14.     Node    * left;  
15.     Node    * right;  
16.     Node():left(NULL), right(NULL) , freq(0) , val('0'){}  
17. };  
18.   
19. class Cmp  
20. {  
21. public:  
22.     bool operator() (const Node * a, const Node * b) const  
23.     {  
24.         return  a->freq > b->freq;  // 从小到大 ，freq 小的 优先级别高    
25.     }  
26. };  
27.   
28. priority_queue<Node* , vector<Node*> , Cmp> myQueue;  
29.   
30. void BuildTree()  
31. {  
32.     for (int i = 0; i < 26; ++ i)  
33.     {  
34.         if (Table[i] > 0)  
35.         {  
36.             Node * node = new Node();  
37.             node->freq = Table[i];  
38.             node->val =(char) (i + 'A');  
39.             myQueue.push(node);  
40.         }  
41.     }  
42.       
43.     while (myQueue.size() > 1)  
44.     {  
45.         Node * f = myQueue.top();  
46.         myQueue.pop();  
47.         Node * s = myQueue.top();  
48.         myQueue.pop();  
49.         Node * tmp = new Node();  
50.         tmp->freq = f->freq + s->freq;  
51.         tmp->left = f;  
52.         tmp->right = s;  
53.         myQueue.push(tmp);  
54.     }  
55.     //cout << myQueue.top()->freq<<endl;   
56. }  
57.   
58. struct PrintNode  
59. {  
60.     int freq;   
61.     char val;  
62.     string code;  
63. };  
64.   
65. vector<PrintNode> vpn;  
66. bool cmp(const PrintNode & a , const PrintNode & b)  
67. {  
68.     return a.freq > b.freq;  
69. }  
70.   
71. void Print( Node * node , string res)  
72. {  
73.     if (node == NULL)  
74.     {  
75.         return;  
76.     }  
77.     if (node->val != '0')  
78.     {  
79.         PrintNode pn;  
80.         pn.val = node->val;  
81.         pn.freq = node->freq;  
82.         pn.code = res;  
83.         vpn.push_back(pn);  
84.         //cout <<node->val <<" | " << node->freq <<" | "<< res <<endl;   
85.         return ;  
86.     }  
87.     Print(node->left , res + "0");  
88.     Print(node->right, res + "1");  
89.     delete node->left;  
90.     delete node->right;  
91. }  
92.   
93. int main()  
94. {  
95.     int N;  
96.     memset(Table , 0 , sizeof(Table));  
97.     cin >> N;  
98.     for (int i = 0; i < N; ++i)  
99.     {  
100.         char ch ;  
101.         cin >> ch;  
102.         if (ch >= 'A' && ch <= 'Z')  
103.         {  
104.             ++Table[ch - 'A'];  
105.         }  
106.     }  
107.     BuildTree();  
108.     Node * root = myQueue.top();  
109.     myQueue.pop();  
110.     Print(root , "");  
111.       
112.     sort(vpn.begin() , vpn.end() , cmp);  
113.       
114.     for (int i = 0; i < vpn.size(); ++i)  
115.     {  
116.         cout <<vpn[i].val << " "<<vpn[i].freq <<" " << vpn[i].code<<endl;  
117.     }  
118.     return 0;  
119. }