#include<bits/stdc++.h>
using namespace std;
struct Node
{
char data;
int freq;
Node *left,*right;
Node(char c,int d)
{
data=c;
freq=d;
left = right = nullptr;
}
};
struct compare {
bool operator()(Node* l, Node* r) {
return l->freq > r->freq;
}
};
void generatebinarycode(Node *root,string s,map<char,string>&huffmancode)
{
if(root==nullptr) return;
if(root->left==nullptr&&root->right==nullptr)
{
huffmancode[root->data]=s;
return;
}
generatebinarycode(root->left,s+'0',huffmancode);
generatebinarycode(root->right,s+'1',huffmancode);
}
Node *buildhyfman(string &s,map<char,string>&huffmancode)
{
map<char,int>mp;
for(int i=0;i<s.size();i++)
{
mp[s[i]]++;
}
priority_queue<Node *,vector<Node *>,compare>pq;
for(auto u:mp)
{
pq.push(new Node(u.first,u.second));
}
while (pq.size()>1)
{
Node *l=pq.top();
pq.pop();
Node *r=pq.top();
pq.pop();
Node *newnode=new Node('*',l->freq+r->freq);
newnode->left=l;
newnode->right=r;
pq.push(newnode);
}
Node *root=pq.top();
generatebinarycode(root,"",huffmancode);
return root;
}
int main()
{
string s;
getline(cin,s);
map<char,string>huffmancode;
Node *root=buildhyfman(s,huffmancode);
string encodestring="";
for(int i=0;i<s.size();i++)
{
encodestring+=huffmancode[s[i]];
}
cout<<encodestring<<endl;
//this is for decoding
map<string,char>huffmandecode;
for(auto u:huffmancode)
{
huffmandecode[u.second]=u.first;
}
string temp="";
for(int i=0;i<encodestring.size();i++)
{
temp+=encodestring[i];
if(huffmandecode.find(temp)!=huffmandecode.end())
{
cout<<huffmandecode[temp];
temp="";
}
}
return 0;
}
0 Comments