HUFFMAN ALGORITHM

The Huffman algorithm is a basic algorithm to represent the data stream in a tree. It is arranged according to the frequencies of the data.

Source code for Huffman Algorithm implemented in C++

#include<iostream>

#include<queue>

using namespace std;

class Node {

    private:

        float m_pro;

        bool m_value;

        Node* m_father;

        string m_sym;

    public:

        Node(string& sym,float pro):m_pro(pro),m_value(false),m_father(NULL),m_sym(sym){}

        Node(Node& a,Node& b,bool value=0):m_father(NULL),m_value(false),m_sym(""){

            m_pro = a.m_pro+b.m_pro;

            a.m_father = b.m_father = this;

            a.m_value = false;

            b.m_value = true;

        }

        float probability() const {

            return m_pro;

        }

        bool value() const{

            return m_value;

        }

        string symbol() const{

            return m_sym;

        }

        Node* father() const{

            return m_father;

        }

};

class NodeCompare {

    public:

        // Acts a < for determining priority

        bool operator()(Node* n1,Node* n2) const {

            if( n1->probability() > n2->probability() ) return true;

            return false;

        }

};

int main(){

    unsigned n;

    std::cout << "Enter the no. of entries: ";

    std::cin >> n;

    if( n == 1){

        std::cout << "1! You're joking, right?";

        return 0;

    }

    Node** list = new Node*[2*n];

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

    unsigned j;

    for(j=0;j<n;j++){

        string symbol;

        float pro;

        std::cout << "Enter the Symbol and Probability: ";

        std::cin >> symbol >> pro;

        list[j] = new Node(symbol,pro);

        pq.push(list[j]);

    }

    while(pq.size() > 1) {

        Node* one = const_cast<Node*>(pq.top());

        pq.pop();

        Node* two = const_cast<Node*>(pq.top());

        pq.pop();

        list[j] = new Node(*one,*two);

        pq.push(list[j]);

        j++;

    }

    pq.pop();

    for(int i=0;i<n;i++){

        std::cout << list[i]->symbol() << ": ";

        Node one = *list[i];

        while( one.father() != NULL){

            std::cout << one.value();

            one = *one.father();

        }

        std::cout << std::endl;

    }

    for(int i=0;i<j;i++)

        delete list[j];

    delete []list;

    return 0;

}