Other/Huffman Coding.cpp
void build_queue()
{
    queue< TreeNode* > leaves;
    queue< TreeNode* > inner;
    // Sorting the chars by their freqs
    vector< pair<char, double> > chars;
    for(auto &x: freq)
    {
        chars.push_back(x);
    }
    sort(chars.begin(), chars.end(), freqCmp);
    // create all the leaves
    for(auto &x: chars)
    {
        loc[x.first] = new TreeNode(x.first, x.second);
        leaves.push(loc[x.first]);
    }
    // merge
    while(leaves.size() + inner.size() > 1)
    {
        cout<<leaves.size()<<" "<<inner.size()<<endl;
        TreeNode *a, *b;
        // pick a
        if( !leaves.empty() && (inner.empty() || leaves.front() -> prob < inner.front() -> prob) )
        {
            a = leaves.front();
            leaves.pop();
        }
        else
        {
            a = inner.front();
            inner.pop();
        }
        // pick b
        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);
    }
    // set the root
    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
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