For a set of messages M1,...,Mn with given frequencies as input, implement the c

Question

For a set of messages M1,...,Mn with given frequencies as input, implement the construction of a Huffman tree by consecutively combining the next two subtrees of smallest weight. Use a heap as a priority queue. Construct Huffman codes as binary strings for the given messages. Print the codes and the weighted average codeword length. Run your program for the example of the frequencies of letter occurrences in the English alphabet, and for the Exercise #4 of Section 4.8 in Version 2 HSR (Huffman decode tree and codes for messages (M1,...,M7) with frequencies (q1,...,q7) = (4,5,7,8,10,12,20)). need help in c++

Explanation / Answer

#include <bits/stdc++.h>
using namespace std;

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 << " ";

    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()
{

    char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int freq[] = { 5, 10, 12, 14, 16, 47 };

    int size = sizeof(arr) / sizeof(arr[0]);

    HuffmanCodes(arr, freq, size);

    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.