#include<bits/stdc++.h>
#define char_num 6
using namespace std;
typedef struct Tree{
  string name_;
  int weight_;
  struct Tree* left, *right;
}*BinTree;
struct cmp{
   bool operator()(const BinTree& a,const BinTree& b){
       return a->weight_ > b->weight_;
   }
};
priority_queue<BinTree,vector<BinTree>,cmp> que;
string str[char_num] = {"a", "b", "c", "d", "e", "f"};
int weight[char_num] = {45, 13, 12, 16, 9, 5};
void Init(){
    for(int i=0;i<char_num;i++){
        BinTree t = new struct Tree;
        t->name_ = str[i];
        t->weight_ = weight[i];
        t->left = NULL;
        t->right = NULL;
        que.push(t);
    }

}
BinTree Build_Tree(BinTree t1,BinTree t2){
    BinTree t = new struct Tree;//new space for the pointer
    t->left = t1;
    t->right = t2;
    t->weight_ = t1->weight_ + t2->weight_;
    return t;
}
void Build_Huffman_Tree(){
    for(int i=0;i<char_num-1;i++){
        BinTree t1,t2,t;
        t1 = que.top();
        que.pop();
        t2 = que.top();
        que.pop();
        t = Build_Tree(t1,t2);
        que.push(t);
    }
 }
void Print_Huffman_code(BinTree T,string code){
    if(T){
        if(!T->left&&!T->right){
        cout<<T->name_<<" "<<code<<endl;
        }
    Print_Huffman_code(T->left,code + "0");
    Print_Huffman_code(T->right,code + "1");
    }

    return;

}
int main(){
    Init();
    Build_Huffman_Tree();
    BinTree T = que.top();
    cout<<"Huffman coding is"<<endl;
    Print_Huffman_code(T,"");
    return 0;
}