Other/Huffman Coding.cpp
// Building the Huffman Tree using the queue method
// O(N) but we still need O(NlogN) to sort
Building the Huffman Tree using the queue method
O(N) but we still need O(NlogN) to sort
Building the Huffman Tree using the queue method O ( N ) but we still need O ( NlogN ) to sort
void build_queue()
{
    queue< TreeNode* > leaves;
    queue< TreeNode* > inner;
    vector< pair<char, double> > chars;
    for(auto &x: freq)
    {
        chars.push_back(x);
    }
    sort(chars.begin(), chars.end(), freqCmp);
    for(auto &x: chars)
    {
        loc[x.first] = new TreeNode(x.first, x.second);
        leaves.push(loc[x.first]);
    }
    while(leaves.size() + inner.size() > 1)
    {
        cout<<leaves.size()<<" "<<inner.size()<<endl;
        TreeNode *a, *b;
        if( !leaves.empty() && (inner.empty() || leaves.front() -> prob < inner.front() -> prob) )
        {
            a = leaves.front();
            leaves.pop();
        }
        else
        {
            a = inner.front();
            inner.pop();
        }
        if( !leaves.empty() && (inner.empty() || leaves.front() -> prob < inner.front() -> prob) )
        {
            b = leaves.front();
            leaves.pop();
        }
        else
        {
            b = inner.front();
            inner.pop();
        }
        TreeNode* nw = new TreeNode(a, b);
        a -> parent = b -> parent = nw;
        inner.push(nw);
    }
    root = inner.front();
    return;
}
void build_queue ( ) { queue < TreeNode * > leaves ; queue < TreeNode * > inner ; vector < pair < char , double > > chars ; for ( auto & x : freq ) { chars . push_back ( x ) ; } sort ( chars . begin ( ) , chars . end ( ) , freqCmp ) ; for ( auto & x : chars ) { loc [ x . first ] = new TreeNode ( x . first , x . second ) ; leaves . push ( loc [ x . first ] ) ; } while ( leaves . size ( ) + inner . size ( ) > 1 ) { cout << leaves . size ( ) << " " << inner . size ( ) << endl ; TreeNode * a , * b ; if ( ! leaves . empty ( ) && ( inner . empty ( ) || leaves . front ( ) -> prob < inner . front ( ) -> prob ) ) { a = leaves . front ( ) ; leaves . pop ( ) ; } else { a = inner . front ( ) ; inner . pop ( ) ; } if ( ! leaves . empty ( ) && ( inner . empty ( ) || leaves . front ( ) -> prob < inner . front ( ) -> prob ) ) { b = leaves . front ( ) ; leaves . pop ( ) ; } else { b = inner . front ( ) ; inner . pop ( ) ; } TreeNode * nw = new TreeNode ( a , b ) ; a -> parent = b -> parent = nw ; inner . push ( nw ) ; } root = inner . front ( ) ; return ; }
Building the Huffman Tree using the queue method
O(N) but we still need O(NlogN) to sort
Building the Huffman Tree using the queue method O ( N ) but we still need O ( NlogN ) to sort
// Sorting the chars by their freqs // create all the leaves // merge // pick a // pick b // set the root