#include <iostream>
#include <string>	
#include <fstream>
#include <sstream>
#include <vector>       
#include <algorithm>
#include <memory>
#include <iomanip>
#include <cassert>

struct node;
using node_handle = std::unique_ptr<node>;

struct node
{
    char data;
    std::size_t frequency;

    node_handle left;
    node_handle right;

    node(std::size_t freq) : data('\0'), frequency(freq) {}
    node(char ch, std::size_t freq) : data(ch), frequency(freq) {}

    bool operator<(const node& n) { return frequency < n.frequency; }

    bool isLeaf() const { return left == nullptr && right == nullptr;}
};

std::vector<node_handle> extractHuffmanData(std::istream& is)
{
    std::vector<node_handle> data;

    std::size_t frequency;
    char ch;

    while (is >> ch >> frequency)
        data.emplace_back(new node(ch, frequency));

    return data;
}

node_handle buildHuffmanTree(std::vector<node_handle> data)
{
    assert(data.size() > 0);

    auto comp = [](const node_handle& a, const node_handle& b)    
    { 
        return *a < *b; 
    };

    std::sort(data.begin(), data.end(), comp);

    while (data.size() > 1)
    {
        node_handle a(data[0].release());
        node_handle b(data[1].release());
        data.erase(data.begin(), data.begin() + 2);

        node_handle parent(new node(a->frequency + b->frequency));
        parent->left.swap(a);
        parent->right.swap(b);

        auto pos = std::lower_bound(data.begin(), data.end(), parent, comp);
        data.emplace(pos, parent.release());
    }

    return node_handle(data.back().release());
}

void print(const node_handle& node, std::size_t indent_level=0)
{
    if (node == nullptr)
        return;

    const size_t indent_width = 2;
    std::cout << std::setw(indent_width * indent_level) << "";
    std::cout << node->frequency;

    if (node->isLeaf())
        std::cout << " - " << node->data << '\n';
    else
    {
        std::cout << '\n';
        print(node->left, indent_level + 1);
        print(node->right, indent_level + 1);
    }
}

int main()
{
    std::istringstream is
    {
        "a 119\n"
        "b 20\n"
        "c 44\n"
        "d 127\n"
    };

    auto huffmanData = extractHuffmanData(is);
    auto huffmanTree = buildHuffmanTree(std::move(huffmanData));

    print(huffmanTree);
}