#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
using namespace std;
 
// Node structure for Huffman Tree
struct Node {
    char ch;
    int freq;
    Node *left, *right;
    Node(char ch, int freq, Node* left = nullptr, Node* right = nullptr) {
        this->ch = ch;
        this->freq = freq;
        this->left = left;
        this->right = right;
    }
};
 
// Custom comparator to make min-heap
struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};
 
// Recursive function to generate Huffman Codes
void buildCodes(Node* root, string code, unordered_map<char, string>& huffCode) {
    if (!root) return;
    // If it's a leaf node
    if (!root->left && !root->right) {
        huffCode[root->ch] = code;
        return;
    }
    buildCodes(root->left, code + "0", huffCode);
    buildCodes(root->right, code + "1", huffCode);
}
 
int main() {
    string input;
    cout << "Enter the string: ";
    cin >> input;
    // Step 1: Count frequency of each character
    unordered_map<char, int> freq;
    for (char ch : input) {
        freq[ch]++;
    }
    // Step 2: Create priority queue (min-heap) of Nodes
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto it : freq) {
        Node* newNode = new Node(it.first, it.second);
        pq.push(newNode);
    }
    // Step 3: Build Huffman Tree
    while (pq.size() > 1) {
        Node* node1 = pq.top(); pq.pop();
        Node* node2 = pq.top(); pq.pop();
        Node* parent = new Node('\0', node1->freq + node2->freq, node1, node2);
        pq.push(parent);
    }
    Node* root = pq.top();  // Final root of Huffman Tree
    // Step 4: Generate Huffman Codes
    unordered_map<char, string> huffCode;
    buildCodes(root, "", huffCode);
    // Step 5: Display Huffman Codes
    cout << "\nHuffman Codes:\n";
    for (auto pair : huffCode) {
        cout << pair.first << " → " << pair.second << endl;
    }
    return 0;
}