huffman_code

#include<iostream>
#include <fstream>
#include<vector>
#include<algorithm>
#include<queue>
#include<functional>
#include<string>
using namespace std;

ifstream f("file.txt");
struct MinHeapNode {

    char data;
    unsigned freq;
    MinHeapNode *left, *right;
    MinHeapNode(char data, unsigned freq)

    {

        left = right = NULL;
        this->data = data;
        this->freq = freq;
    }
};


struct compare {

    bool operator()(MinHeapNode* l, MinHeapNode* r)

    {
        return (l->freq > r->freq);
    }
};

void printCodes(struct MinHeapNode* root, string str)
{

    if (!root)
        return;

    if (root->data != '$')
        cout << root->data << ": " << str << "\n";

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


void HuffmanCodes(char data[], int freq[], int size)
{
    struct MinHeapNode *left, *right, *top;


    priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;

    for (int i = 0; i < size; ++i)
        minHeap.push(new MinHeapNode(data[i], freq[i]));
    while (minHeap.size() != 1) {


        left = minHeap.top();
        minHeap.pop();

        right = minHeap.top();
        minHeap.pop();


        top = new MinHeapNode('$', left->freq + right->freq);

        top->left = left;
        top->right = right;

        minHeap.push(top);
    }

    printCodes(minHeap.top(), "");
}


int main()
{
    int v[200];
    for (int i = 'a'; i<'z'; i++)
        v[i] = 0;
    int dim = 0;
    char s;
    while (f >> s)
    {
        dim++;
        v[s]++;
    }

    char arr[100];
    int freq[100];
    int con = 0;
    for (char i = 'a'; i<'z'; i++)
        if (v[i]>0)
        {
            arr[con] = i;

            freq[con] = v[i];
            con++;
        }
    arr[con]='\0';
    int size = con;
    HuffmanCodes(arr, freq, size);

    return 0;
}