// in c++ object is equivalent to pointer keep this in mind so when creating object with
//new keyword keep in mind it will return a pointer
#include<bits/stdc++.h>
#define ull unsigned long long
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
struct node
{
pair<int,char> p;
node *l,*r;
node(char c,int freq)
{
l=r=NULL;
this->p.first=freq;
this->p.second=c;
}
};
struct compare
{
bool operator()(node *a,node *b)
{
return (a->p.first > b->p.first);
}
};
void printCodes(node* root, string str)
{
if (!root)
return;
if (root->p.second != '$')
cout << root->p.second << ": " << str << "\n";
printCodes(root->l, str + "0");
printCodes(root->r, str + "1");
}
int main()
{
ios::sync_with_stdio(false);
//cin.tie(NULL);
cout<<"Enter No of characters: ";
int n,freq;
char c;
cin>>n;
cout<<"Enter chars along with their frequencies: \n";
priority_queue<node*,vector<node* >,compare> pq;
for(int i=0;i<n;i++)
{
cin>>c>>freq;
pq.push(new node(c,freq));
}
node *t,*lef,*rig;
while(pq.size()!=1)
{
lef=pq.top();
pq.pop();
rig=pq.top();
pq.pop();
t=new node('$',lef->p.first+rig->p.first);
t->l=lef;
t->r=rig;
pq.push(t);
}
//cout<<"SuccessFull insertion:)";
printCodes(pq.top(),"");
}
Ly8gaW4gYysrIG9iamVjdCBpcyBlcXVpdmFsZW50IHRvIHBvaW50ZXIga2VlcCB0aGlzIGluIG1pbmQgc28gd2hlbiBjcmVhdGluZyBvYmplY3Qgd2l0aAovL25ldyBrZXl3b3JkIGtlZXAgaW4gbWluZCBpdCB3aWxsIHJldHVybiBhIHBvaW50ZXIKI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSB1bGwgdW5zaWduZWQgbG9uZyBsb25nCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgcGFpcjxpbnQsaW50PiBwaWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CgpzdHJ1Y3Qgbm9kZQp7CglwYWlyPGludCxjaGFyPiBwOwoJbm9kZSAqbCwqcjsKCW5vZGUoY2hhciBjLGludCBmcmVxKQoJewoJCWw9cj1OVUxMOwoJCXRoaXMtPnAuZmlyc3Q9ZnJlcTsKCQl0aGlzLT5wLnNlY29uZD1jOwoJfQp9OwoKc3RydWN0IGNvbXBhcmUKewoJYm9vbCBvcGVyYXRvcigpKG5vZGUgKmEsbm9kZSAqYikKCXsKCQlyZXR1cm4gKGEtPnAuZmlyc3QgPiBiLT5wLmZpcnN0KTsKCX0KfTsKdm9pZCBwcmludENvZGVzKG5vZGUqIHJvb3QsIHN0cmluZyBzdHIpCnsKICAgIGlmICghcm9vdCkKICAgICAgICByZXR1cm47CiAKICAgIGlmIChyb290LT5wLnNlY29uZCAhPSAnJCcpCiAgICAgICAgY291dCA8PCByb290LT5wLnNlY29uZCA8PCAiOiAiIDw8IHN0ciA8PCAiXG4iOwogCiAgICBwcmludENvZGVzKHJvb3QtPmwsIHN0ciArICIwIik7CiAgICBwcmludENvZGVzKHJvb3QtPnIsIHN0ciArICIxIik7Cn0KaW50IG1haW4oKQp7Cglpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgkvL2Npbi50aWUoTlVMTCk7Cgljb3V0PDwiRW50ZXIgTm8gb2YgY2hhcmFjdGVyczogIjsKCWludCBuLGZyZXE7CgljaGFyIGM7CgljaW4+Pm47Cgljb3V0PDwiRW50ZXIgY2hhcnMgYWxvbmcgd2l0aCB0aGVpciBmcmVxdWVuY2llczogXG4iOwoJcHJpb3JpdHlfcXVldWU8bm9kZSosdmVjdG9yPG5vZGUqID4sY29tcGFyZT4gcHE7Cglmb3IoaW50IGk9MDtpPG47aSsrKQoJewoJCWNpbj4+Yz4+ZnJlcTsKCQlwcS5wdXNoKG5ldyBub2RlKGMsZnJlcSkpOwoJfQoJbm9kZSAqdCwqbGVmLCpyaWc7Cgl3aGlsZShwcS5zaXplKCkhPTEpCgl7CgkJbGVmPXBxLnRvcCgpOwoJCXBxLnBvcCgpOwoJCXJpZz1wcS50b3AoKTsKCQlwcS5wb3AoKTsKCQl0PW5ldyBub2RlKCckJyxsZWYtPnAuZmlyc3QrcmlnLT5wLmZpcnN0KTsKCQl0LT5sPWxlZjsKCQl0LT5yPXJpZzsKCQlwcS5wdXNoKHQpOwoJfQoJLy9jb3V0PDwiU3VjY2Vzc0Z1bGwgaW5zZXJ0aW9uOikiOwoJcHJpbnRDb2RlcyhwcS50b3AoKSwiIik7Cn0K