saim_s_huffman

#include<bits/stdc++.h>
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
long long int i=0;

map<char,string>huffmanCode;
string s;

string generate_id(string s)
{
    string id="MYIDIS";
    map<char,string>mp;
    mp['0']="ZERO",mp['1']="ONE",mp['2']="TWO",mp['3']="THREE",mp['4']="FOUR",mp['5']="FIVE",mp['6']="SIX",mp['7']="SEVEN",
                                         mp['8']="EIGHT",mp['9']="NINE";


    for(i=s.size()-4; i<s.size(); i++)
    {
        id+=mp[s[i]];
    }
    return id;
}


struct Node
{
    char ch;
    int freq;
    Node *left, *right;
};

// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
    Node* node = new Node();

    node->ch = ch;
    node->freq = freq;
    node->left = left;
    node->right = right;

    return node;
}



struct comp
{
    bool operator()(Node* l, Node* r)
    {
        return l->freq > r->freq;
    }
};




void  encode(Node* root, string str)
{
    if (root ==NULL)
        return;

    if (!root->left && !root->right)
    {
        huffmanCode[root->ch] = str;
    }

    encode(root->left, str + "0");
    encode(root->right, str + "1");
}



void buildHuffmanTree(string text)
{
    map<char, int> freq;
    for (char ch: text)
    {
        freq[ch]++;
    }

    priority_queue<Node*, vector<Node*>, comp> pq;

    for (auto pair: freq)
    {
        pq.push(getNode(pair.first, pair.second, NULL, NULL));
    }

    while (pq.size() != 1)
    {
        Node *left = pq.top();
        pq.pop();
        Node *right = pq.top();
        pq.pop();
        int sum = left->freq + right->freq;
        pq.push(getNode('\0', sum, left, right));
    }

    Node* root = pq.top();

    encode(root, "");

    int frequ[26]={0};

    string st=generate_id(s);
    string temp;
    for(i=0;i<st.size();i++)
    {
        if(!frequ[st[i]-'A'])
        {
            temp+=st[i];
            frequ[st[i]-'A']++;
        }
    }

    cout<<endl;


    for(auto x:temp)
    {
        cout<<"        "<<x<<":"<<"  "<<huffmanCode[x]<<endl;
    }

}

int main()
{

    cout<<"Step #1.Enter Student ID:";
    cin>>s;
    cout<<"Step #2.Generated String:"<<generate_id(s)<<endl;
    cout<<"Step #3.Prefix Codes(Generated Using Huffman Coding):";
    buildHuffmanTree(generate_id(s));
    return 0;
}