-
Notifications
You must be signed in to change notification settings - Fork 0
/
Huffman Encoding
80 lines (68 loc) · 1.33 KB
/
Huffman Encoding
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
struct minHeap
{
char symbol;
int f;
struct minHeap *left;
struct minHeap *right;
minHeap(char sy,int fr)
{
symbol=sy;
f=fr;
this->left=this->right=NULL;
}
};
struct compare
{
bool operator()(minHeap* left,minHeap* right)
{
return left->f > right->f;
}
};
void print(minHeap* root,string str)
{
if(root==NULL)
return;
if(root->symbol!='#')
{
cout<<str<<' ';
}
print(root->left,str+"0");
print(root->right,str+"1");
}
int main()
{
//code
int t;
cin >> t;
while(t--)
{
string s;
cin >> s;
int n=s.length();
int freq[n];
for(int i=0;i<n;i++)
cin >> freq[i];
priority_queue<minHeap*,vector<minHeap*>,compare>pq;
for(int i=0;i<n;i++)
{
pq.push(new minHeap(s[i],freq[i]));
}
while(pq.size() > 1)
{
minHeap* ll=pq.top();
pq.pop();
minHeap* rr=pq.top();
pq.pop();
minHeap *curr= new minHeap('#',ll->f + rr->f);
curr->left=ll;
curr->right=rr;
pq.push(curr);
}
minHeap* root= pq.top();
print(root,"");
cout<<'\n';
}
return 0;
}