#include <iostream>
#include <queue>

using namespace std;

// Вузол бінарного дерева для зберігання частот символів
struct TreeNode {
    char ch;
    int freq;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// Додає вузли в бінарне дерево пошуку
TreeNode* insert(TreeNode* root, char ch, int freq) {
    if (!root) return new TreeNode(ch, freq);
    
    if (ch < root->ch)
        root->left = insert(root->left, ch, freq);
    else if (ch > root->ch)
        root->right = insert(root->right, ch, freq);
    else
        root->freq++; // Якщо символ вже є, збільшити його частоту
    
    return root;
}

// Пошук символу в дереві
TreeNode* find(TreeNode* root, char ch) {
    if (!root) return nullptr;
    if (root->ch == ch) return root;
    
    if (ch < root->ch)
        return find(root->left, ch);
    return find(root->right,ch);
}

// Побудова дерева Хаффмана
struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode* left;
    HuffmanNode* right;
    
    HuffmanNode(char c, int f, HuffmanNode* l = nullptr, HuffmanNode* r = nullptr)
        : ch(c), freq(f), left(l), right(r) {}
};

struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// Функція обходу дерева частот та додавання вузлів у пріоритетну чергу
void traverse(TreeNode* node, priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare>& pq) {
    if (!node) return;

    pq.push(new HuffmanNode(node->ch, node->freq));
    traverse(node->left, pq);
    traverse(node->right, pq);
}

// Генерація кодів Хаффмана
void generateCodes(HuffmanNode* root, string code, vector<pair<char, string>>& codes) {
    if (!root) return;
    if (root->ch != '\0')
        codes.emplace_back(root->ch, code);
    
    generateCodes(root->left, code + "0", codes);
    generateCodes(root->right, code + "1", codes);
}

int main() {
    string text = "KCENIIAMAZURENKO";
    
    // Створення дерева частот символів
    TreeNode* freqTree = nullptr;
    for (char ch : text) {
        TreeNode* node = find(freqTree, ch);
        if (node)
            node->freq++;
        else
            freqTree = insert(freqTree, ch, 1);
    }

    // Створення черги для побудови дерева Хаффмана
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    traverse(freqTree, pq);

    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq, left, right);
        pq.push(parent);
    }

    HuffmanNode* root = pq.top();
    vector<pair<char, string>> huffmanCodes;
    generateCodes(root, "", huffmanCodes);

    // Вивід кодів
    cout << "Коди Хаффмана:\n";
    for (const auto& pair : huffmanCodes)
        cout << pair.first << ": " << pair.second << '\n';

    return 0;
}