Huffman Encoding in DSA C++ - Build from Scratch

Huffman Encoding

📖 Scenario: You work for a company that wants to compress text messages to save space. Huffman encoding is a way to assign shorter codes to frequent letters and longer codes to rare letters, making the message smaller.Imagine you have a small text and want to build the Huffman tree to find the codes for each letter.

🎯 Goal: Build a Huffman tree from given character frequencies and print the Huffman codes for each character.

📋 What You'll Learn

Create a map of characters with their frequencies

Create a priority queue to build the Huffman tree

Build the Huffman tree by combining nodes with smallest frequencies

Traverse the tree to assign codes to each character

Print the Huffman codes for all characters

💡 Why This Matters

🌍 Real World

Huffman encoding is used in file compression formats like ZIP and image formats like JPEG to reduce file size by assigning shorter codes to frequent data.

💼 Career

Understanding Huffman encoding helps in roles involving data compression, storage optimization, and efficient data transmission.

1

Create the frequency map

Create a std::map called freq with these exact entries: 'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45.

DSA C++

# Create the frequency map called freq
// Your code here

Hint

Use std::map freq = {{'a', 5}, {'b', 9}, ...}; to create the frequency map.

2

Define the Huffman tree node and priority queue

Define a struct called Node with char ch, int freq, and Node* left, Node* right. Then create a struct Compare with operator() to compare nodes by frequency. Finally, create a std::priority_queue, Compare> called pq.

DSA C++

#include 
#include 
#include 
#include 

int main() {
    std::map freq = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};

    // Define Node struct, Compare struct, and priority queue pq here
    // Your code here

    return 0;
}

Hint

Define Node with constructor, then Compare with operator() returning true if first freq is greater. Use these in priority queue pq.

3

Build the Huffman tree

Insert all characters from freq into pq as Node pointers. Then, while pq.size() > 1, remove two nodes with smallest frequencies, create a new Node with frequency sum and these two as children, and push it back to pq. Store the final node in root.

DSA C++

#include 
#include 
#include 
#include 

struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

int main() {
    std::map freq = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};

    std::priority_queue, Compare> pq;

    // Insert nodes from freq into pq
    // Build Huffman tree by combining two smallest nodes until one remains
    // Store the final node in root
    // Your code here

    return 0;
}

Hint

Push all freq pairs as nodes into pq. Then combine two smallest nodes repeatedly until one node remains as root.

4

Print Huffman codes by traversing the tree

Write a recursive function printCodes(Node* root, std::string code) that prints each character and its code. If root is null, return. If root->ch is not '\0', print root->ch and code. Recursively call printCodes on root->left with code + '0' and on root->right with code + '1'. Call printCodes(root, "") in main.

DSA C++

#include 
#include 
#include 
#include 

struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

void printCodes(Node* root, std::string code) {
    // Your code here
}

int main() {
    std::map freq = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};

    std::priority_queue, Compare> pq;

    for (auto& pair : freq) {
        pq.push(new Node(pair.first, pair.second));
    }

    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* merged = new Node('\0', left->freq + right->freq);
        merged->left = left;
        merged->right = right;
        pq.push(merged);
    }

    Node* root = pq.top();

    printCodes(root, "");

    return 0;
}

Hint

Use recursion to print codes. If node is leaf (character not '\0'), print character and code. Traverse left with code + '0', right with code + '1'.

Practice

1. What is the main purpose of Huffman Encoding in data compression?

easy

A. To sort characters alphabetically

B. To assign equal length codes to all characters

C. To encrypt data for security

D. To assign shorter codes to more frequent characters

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding aims to reduce the total number of bits by giving shorter codes to characters that appear more often.

2. Step 2: Compare options with this goal

   Only To assign shorter codes to more frequent characters matches this goal. Options A, B, and C do not describe Huffman Encoding correctly.

3. Final Answer:

   To assign shorter codes to more frequent characters -> Option D

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

Hint: Remember: frequent chars get shorter codes [OK]

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing encoding with encryption
• Assuming sorting is the main goal

2. Which of the following C++ code snippets correctly declares a priority queue to build a Huffman tree based on character frequencies?

easy

A. std::priority_queue, std::vector>, std::greater<>> pq;

B. std::priority_queue> pq;

C. std::priority_queue> pq;

D. std::priority_queue, std::vector>, std::less<>> pq;

Solution

1. Step 1: Identify priority queue type for Huffman

   Huffman requires a min-heap priority queue to get the smallest frequency first. std::greater<> creates a min-heap.

2. Step 2: Check each option

   std::priority_queue, std::vector>, std::greater<>> pq; uses std::greater<> with pair, which is correct. Options B and C default to max-heap. std::priority_queue, std::vector>, std::less<>> pq; uses std::less<> which is max-heap.

3. Final Answer:

   std::priority_queue, std::vector>, std::greater<>> pq; -> Option A

4. Quick Check:

   Min-heap priority queue = std::priority_queue, std::vector>, std::greater<>> pq; [OK]

Hint: Use std::greater<> for min-heap in priority_queue [OK]

Common Mistakes:

• Using default max-heap instead of min-heap
• Swapping pair elements order incorrectly
• Forgetting to specify comparator

3. Given the frequencies: {'a': 5, 'b': 9, 'c': 12, 'd': 13}, what is the Huffman code for character 'a' after building the Huffman tree?

medium

A. 111

B. 00

C. 110

D. 10

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies: 5('a') + 9('b') = 14, then combine 12('c') + 13('d') = 25, then combine 14 + 25 = 39.

2. Step 2: Assign codes from tree

   'a' is in the left subtree of the first combined node, so it gets code '110' (left-right-left). Other codes differ.

3. Final Answer:

   110 -> Option C

4. Quick Check:

   'a' gets code = 110 [OK]

Hint: Lowest freq chars get codes with more leading zeros [OK]

Common Mistakes:

• Assigning wrong code by mixing tree branches
• Confusing 'a' code with 'b' or 'c'
• Not building tree stepwise

4. Identify the error in this C++ snippet for building a Huffman tree:

std::priority_queue, Compare> pq;
while(pq.size() > 1) {
  Node* left = pq.top(); pq.pop();
  Node* right = pq.top(); pq.pop();
  Node* parent = new Node(left->freq + right->freq, left, right);
  pq.push(parent);
}

medium

A. The loop condition should be pq.size() >= 1

B. The priority queue comparator Compare is missing or incorrect

C. Nodes should be popped after pushing the parent

D. The parent node frequency calculation is wrong

Solution

1. Step 1: Check priority queue usage

   Priority queue needs a comparator to order nodes by frequency ascending for Huffman. If Compare is missing or incorrect, ordering fails.

2. Step 2: Validate other parts

   Loop condition pq.size() > 1 is correct. Popping nodes before pushing parent is correct. Frequency sum is correct.

3. Final Answer:

   The priority queue comparator Compare is missing or incorrect -> Option B

4. Quick Check:

   Missing comparator breaks min-heap order [OK]

Hint: Always define comparator for priority_queue of pointers [OK]

Common Mistakes:

• Using wrong loop condition
• Popping nodes in wrong order
• Incorrect frequency sum

5. You have the string "abbcccdddd". Using Huffman Encoding, what is the total number of bits required to encode this string if the codes are assigned optimally?

hard

A. 19 bits

B. 22 bits

C. 24 bits

D. 20 bits

Solution

1. Step 1: Calculate character frequencies

   'a':1, 'b':2, 'c':3, 'd':4.

2. Step 2: Build Huffman tree and assign codes

   Combine lowest frequencies: 1+2=3, then 3+3=6, then 4+6=10. Codes assigned roughly: 'd' = 1 bit, 'c' = 2 bits, 'b' = 3 bits, 'a' = 3 bits.

3. Step 3: Calculate total bits

   Total bits = (1*3) + (2*3) + (3*2) + (4*1) = 3 + 6 + 6 + 4 = 19 bits.

4. Final Answer:

   19 bits -> Option A

5. Quick Check:

   Total bits = sum(freq * code length) = 19 [OK]

Hint: Multiply frequency by code length, then sum all [OK]

Common Mistakes:

• Mixing frequencies and code lengths
• Assigning wrong code lengths
• Adding frequencies instead of bits