#include<iostream>
#include<utility>
#include<vector>
#include<queue>

using namespace std;

struct node{
	int freq;
	string c;
	node *left,*right;
}*root, *ptr;

struct cmp{
	bool operator()(node* left, node* right){
		if(left->freq== right->freq){
			if((left->c).size()==(right->c).size()){
				return (left->c)< (right->c);
			}
			return (left->c).size()< (right->c).size();
		}
		return left->freq > right->freq;
	}
};

void print(priority_queue<node*, vector <node*>, cmp> q){
	cout<<"Heap State:\n";
    while (!q.empty()){
        cout<<q.top()->c<<" "<<q.top()->freq<< endl;
        q.pop();
    }
    cout<<endl;
}
node* create_node(int freq, string c){
	ptr=new(struct node);
	ptr->freq= freq;
	ptr->c= c;
	ptr->left=NULL;
	ptr->right=NULL;
	return ptr;
}

void gen_code(node *np,string op){
	if (np->left==NULL || np->right==NULL){
		cout<<np->c<<" "<<op<<endl;
		return;
	}
	gen_code(np->left,op+"1");
	gen_code(np->right,op+"0");
}
int main(){
	root=NULL;
	vector< pair<int,string> > v;
	//string s[]={"A","B","C","D","E","F"};
	//int occ[]={ 5, 9, 12, 13, 16, 45 };
	int n;
	cout<<"Enter n: ";
	cin>>n;
	cout<<"Enter character and frequency: \n";
	for (int i=0;i<n;i++){
		string s;
		int occ;
		cin>>s>>occ;
		v.push_back(make_pair(occ,s));
	}
	priority_queue<node*, vector <node*>, cmp> heap;
	for(int i = 0; i < n; i++) {
		node* newptr = create_node(v[i].first, v[i].second);
		heap.push(newptr);
	}
	print(heap);
	while(heap.size() != 1) {
		node* ptr1 = heap.top();
		heap.pop();
		node* ptr2 = heap.top();
		heap.pop();
		int add_freq = (ptr1->freq)+(ptr2->freq);
		string add_char= (ptr1->c)+ (ptr2->c);
		node* parent = create_node(add_freq, add_char);
		parent->left = ptr1;
		parent->right = ptr2;
		heap.push(parent);
		root = parent;
		print(heap);
	}
	cout<<"Codewords: \n";
	gen_code(root,"");
}