Huffman Encoding in DSA C++

Mental Model

Huffman encoding builds a tree to assign shorter codes to frequent letters and longer codes to rare ones, saving space.

Analogy: Imagine packing a suitcase where you put your most used clothes on top for easy access and less used ones at the bottom, so you open the suitcase less to get what you need.

Characters and frequencies:
a:5  b:9  c:12  d:13  e:16  f:45

Initial nodes:
[a:5]  [b:9]  [c:12]  [d:13]  [e:16]  [f:45]

Tree nodes combine smallest frequencies:
[a:5] + [b:9] -> [14]
[c:12] + [d:13] -> [25]
[e:16] + [14] -> [30]
[25] + [30] -> [55]
[f:45] + [55] -> [100]

Root: [100]

Each leaf gets a code from path: left=0, right=1

Dry Run Walkthrough

Input: characters with frequencies: a:5, b:9, c:12, d:13, e:16, f:45

Goal: Build Huffman tree and assign binary codes to each character minimizing total bits

Step 1: Pick two smallest frequencies a:5 and b:9, combine into node 14

[14]  [c:12]  [d:13]  [e:16]  [f:45]

Why: Combine smallest to build tree bottom-up

Step 2: Pick next two smallest c:12 and d:13, combine into node 25

[14]  [25]  [e:16]  [f:45]

Why: Continue combining smallest nodes

Step 3: Pick smallest nodes 14 and e:16, combine into node 30

[25]  [30]  [f:45]

Why: Build higher level nodes

Step 4: Pick smallest nodes 25 and 30, combine into node 55

[55]  [f:45]

Why: Combine to approach root

Step 5: Combine last two nodes 45 and 55 into root 100

[100]

Why: Complete tree with total frequency

Step 6: Assign codes by traversing tree: left=0, right=1

a: 1100
b: 1101
c: 100
d: 101
e: 111
f: 0

Why: Codes reflect path from root to leaves

Result:

Huffman codes:
a:1100
b:1101
c:100
d:101
e:111
f:0

Annotated Code

DSA C++

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

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

struct Compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq; // min-heap by freq
    }
};

void buildCodes(Node* root, const string& str, unordered_map<char, string>& huffmanCode) {
    if (!root) return;

    if (!root->left && !root->right) {
        huffmanCode[root->ch] = str; // leaf node code assignment
    }

    buildCodes(root->left, str + "0", huffmanCode); // left edge adds 0
    buildCodes(root->right, str + "1", huffmanCode); // right edge adds 1
}

void huffmanEncoding(const unordered_map<char, int>& freq) {
    priority_queue<Node*, vector<Node*>, Compare> pq;

    for (auto pair : freq) {
        pq.push(new Node(pair.first, pair.second)); // create leaf nodes
    }

    while (pq.size() != 1) {
        Node* left = pq.top(); pq.pop(); // smallest freq
        Node* right = pq.top(); pq.pop(); // second smallest freq

        Node* sum = new Node('\0', left->freq + right->freq); // internal node
        sum->left = left; // left child
        sum->right = right; // right child

        pq.push(sum); // push combined node back
    }

    Node* root = pq.top();

    unordered_map<char, string> huffmanCode;
    buildCodes(root, "", huffmanCode); // generate codes

    for (auto pair : freq) {
        cout << pair.first << ":" << huffmanCode[pair.first] << "\n";
    }
}

int main() {
    unordered_map<char, int> freq = {{'a',5}, {'b',9}, {'c',12}, {'d',13}, {'e',16}, {'f',45}};
    huffmanEncoding(freq);
    return 0;
}

pq.push(new Node(pair.first, pair.second));

create leaf nodes for each character with frequency

Node* left = pq.top(); pq.pop();

extract smallest frequency node

Node* right = pq.top(); pq.pop();

extract second smallest frequency node

Node* sum = new Node('\0', left->freq + right->freq);

create internal node with combined frequency

sum->left = left; sum->right = right;

assign children to internal node

pq.push(sum);

push combined node back to priority queue

buildCodes(root, "", huffmanCode);

recursively assign codes by traversing tree

if (!root->left && !root->right) { huffmanCode[root->ch] = str; }

assign code string to leaf node character

Output

a:1100

b:1101

c:100

d:101

e:111

f:0

Complexity Analysis

Time: O(n log n) because we insert and extract nodes from a priority queue n times

Space: O(n) for storing nodes and codes where n is number of unique characters

vs Alternative: Compared to fixed-length codes, Huffman reduces average bits by using variable-length codes based on frequency

Edge Cases

Single character input

Code assigned is empty string or '0' since only one node exists

DSA C++

if (!root->left && !root->right) { huffmanCode[root->ch] = str; }

Characters with equal frequencies

Tree structure may vary but codes remain valid and prefix-free

DSA C++

priority_queue with Compare ensures consistent ordering

Empty input frequency map

No output, function exits without error

DSA C++

while (pq.size() != 1) { ... } handles empty pq gracefully

When to Use This Pattern

When you need to compress data by assigning shorter codes to frequent items, reach for Huffman Encoding because it builds an optimal prefix-free code tree.

Common Mistakes

Mistake: Not combining the two smallest frequency nodes first
Fix: Use a min-heap (priority queue) to always pick two smallest nodes

Mistake: Assigning codes only to internal nodes instead of leaves
Fix: Assign codes only at leaf nodes where characters reside

Mistake: Not handling single character input leading to empty code
Fix: Allow empty string or assign '0' code for single character case

Summary

Builds a tree to assign variable-length binary codes minimizing total bits for given character frequencies.

Use when you want to compress data efficiently by encoding frequent characters with shorter codes.

The key insight is combining the two smallest frequency nodes repeatedly to build an optimal prefix-free code tree.

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