Huffman Encoding in DSA C

Mental Model

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

Analogy: Imagine packing a suitcase: you put small, frequent items in easy-to-reach spots and bigger, rare items in harder spots to use space efficiently.

Frequency table: a b c d e
[5] [9] [12] [13] [16]

Initial nodes:
5(a) 9(b) 12(c) 13(d) 16(e)

Tree:
         [55]
        /    \
   [25(cd)]   [30(abe)]
   /    \     /     \
 12(c) 13(d) 14(ab) 16(e)
             /   \
           5(a)  9(b)

Dry Run Walkthrough

Input: string: 'abcde' with frequencies {a:5, b:9, c:12, d:13, e:16}

Goal: Build a Huffman tree to assign binary codes minimizing total bits for encoding

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

Nodes: [14(ab)] [12(c)] [13(d)] [16(e)]

Why: Combine smallest to build tree bottom-up for optimal prefix codes

Step 2: Pick two smallest frequencies 12(c) and 13(d), combine into node with freq 25

Nodes: [14(ab)] [16(e)] [25(cd)]

Why: Continue combining smallest nodes to build tree

Step 3: Pick two smallest frequencies 14(ab) and 16(e), combine into node with freq 30

Nodes: [25(cd)] [30(abe)]

Why: Build higher level nodes by combining smallest frequencies

Step 4: Combine remaining nodes 25(cd) and 30(abe) into root node with freq 55

Root node: [55(abcde)]

Why: Final tree root represents total frequency sum

Step 5: Assign binary codes by traversing tree: left edge = 0, right edge = 1

Codes: a=100, b=101, c=00, d=01, e=11

Why: Assign codes so no code is prefix of another, shortest for frequent chars

Result:

Huffman codes: a=100, b=101, c=00, d=01, e=11

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TREE_HT 100

struct MinHeapNode {
    char data;
    unsigned freq;
    struct MinHeapNode *left, *right;
};

struct MinHeap {
    unsigned size;
    unsigned capacity;
    struct MinHeapNode** array;
};

struct MinHeapNode* newNode(char data, unsigned freq) {
    struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
    temp->left = temp->right = NULL;
    temp->data = data;
    temp->freq = freq;
    return temp;
}

struct MinHeap* createMinHeap(unsigned capacity) {
    struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));
    return minHeap;
}

void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {
    struct MinHeapNode* t = *a;
    *a = *b;
    *b = t;
}

void minHeapify(struct MinHeap* minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < (int)minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
        smallest = left;
    if (right < (int)minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
        smallest = right;
    if (smallest != idx) {
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

int isSizeOne(struct MinHeap* minHeap) {
    return (minHeap->size == 1);
}

struct MinHeapNode* extractMin(struct MinHeap* minHeap) {
    struct MinHeapNode* temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    minHeap->size--;
    minHeapify(minHeap, 0);
    return temp;
}

void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {
    minHeap->size++;
    int i = minHeap->size - 1;
    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = minHeapNode;
}

void buildMinHeap(struct MinHeap* minHeap) {
    int n = minHeap->size - 1;
    for (int i = (n - 1) / 2; i >= 0; --i)
        minHeapify(minHeap, i);
}

int isLeaf(struct MinHeapNode* root) {
    return !(root->left) && !(root->right);
}

struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) {
    struct MinHeap* minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
        minHeap->array[i] = newNode(data[i], freq[i]);
    minHeap->size = size;
    buildMinHeap(minHeap);
    return minHeap;
}

struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {
    struct MinHeapNode *left, *right, *top;
    struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);
    while (!isSizeOne(minHeap)) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        top = newNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}

void printCodes(struct MinHeapNode* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if (isLeaf(root)) {
        printf("%c=", root->data);
        for (int i = 0; i < top; ++i)
            printf("%d", arr[i]);
        printf("\n");
    }
}

int main() {
    char arr[] = {'a', 'b', 'c', 'd', 'e'};
    int freq[] = {5, 9, 12, 13, 16};
    int size = sizeof(arr) / sizeof(arr[0]);
    struct MinHeapNode* root = buildHuffmanTree(arr, freq, size);
    int huffmanCode[MAX_TREE_HT], top = 0;
    printCodes(root, huffmanCode, top);
    return 0;
}

while (!isSizeOne(minHeap)) {

combine two smallest nodes repeatedly to build Huffman tree

left = extractMin(minHeap);

extract smallest frequency node

right = extractMin(minHeap);

extract second smallest frequency node

top = newNode('$', left->freq + right->freq);

create new internal node with combined frequency

top->left = left; top->right = right;

assign children to new node

insertMinHeap(minHeap, top);

insert combined node back into min heap

printCodes(root, huffmanCode, top);

traverse tree to print codes for each character

Output

c=00

d=01

a=100

b=101

e=11

Complexity Analysis

Time: O(n log n) because we build a min heap and extract/insert nodes n-1 times

Space: O(n) for storing nodes and the heap

vs Alternative: Compared to fixed-length encoding, Huffman reduces average bits by assigning shorter codes to frequent chars, saving space

Edge Cases

Single character input

Code assigns 0 to the single character without tree building

DSA C

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

All characters have same frequency

Tree builds but codes may have same length; still valid prefix codes

DSA C

while (!isSizeOne(minHeap)) {

Empty input array

No tree built, program exits or prints nothing

DSA C

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

When to Use This Pattern

When you need to compress data by assigning variable-length codes based on frequency, reach for Huffman Encoding because it builds an optimal prefix code tree.

Common Mistakes

Mistake: Not combining the two smallest frequency nodes each time
Fix: Always extract and combine the two nodes with smallest frequencies from the min heap

Mistake: Assigning codes without ensuring prefix property
Fix: Use tree traversal assigning 0 to left edges and 1 to right edges to guarantee prefix-free codes

Summary

It builds a tree to assign shorter binary codes to frequent characters for efficient encoding.

Use it when you want to compress data by minimizing the total bits needed based on character frequencies.

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

Practice

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

easy

A. To assign equal length codes to all characters

B. To assign shorter codes to more frequent characters

C. To encrypt data for security

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding purpose

   Huffman Encoding compresses data by giving shorter codes to characters that appear more often.

2. Step 2: Compare options with this purpose

   Only To assign shorter codes to more frequent characters matches this goal; others describe different concepts.

3. Final Answer:

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

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

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

Common Mistakes:

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

2. Which data structure is primarily used to build the Huffman tree?

easy

A. Priority Queue (Min-Heap)

B. Stack

C. Queue

D. Hash Table

Solution

1. Step 1: Identify data structure for selecting smallest frequencies

   Huffman tree construction repeatedly picks two smallest frequency nodes.

2. Step 2: Match with data structure that supports this

   Priority Queue (Min-Heap) efficiently provides smallest elements first.

3. Final Answer:

   Priority Queue (Min-Heap) -> Option A

4. Quick Check:

   Smallest freq nodes from Min-Heap [OK]

Hint: Huffman uses Min-Heap to pick smallest frequencies fast [OK]

Common Mistakes:

• Choosing Stack or Queue which don't sort by frequency
• Confusing Hash Table with frequency sorting
• Ignoring the need for smallest frequency extraction

3. What is the output Huffman code for characters with frequencies: A=5, B=9, C=12, D=13, E=16, F=45?

Assuming standard Huffman tree construction, what is the code for character 'F'?

medium

A. 0

B. 10

C. 110

D. 111

Solution

1. Step 1: Build Huffman tree with given frequencies

   Combine smallest pairs: (A=5,B=9)=14, (C=12,D=13)=25, then combine 14 and 16 (E) = 30, then 25 and 30 = 55, finally combine 45 (F) and 55 = 100.

2. Step 2: Assign codes from root; 'F' is combined last and placed on left branch

   Since 'F' has highest frequency, it gets the shortest code '0'.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Highest freq char gets shortest code '0' [OK]

Hint: Highest frequency char gets code '0' in Huffman [OK]

Common Mistakes:

• Assigning longer codes to highest frequency character
• Mixing up left/right branch codes
• Not building tree step-by-step

4. Consider this C code snippet for building a Huffman tree:

struct Node {
  char data;
  int freq;
  struct Node *left, *right;
};

// Function to create a new node
struct Node* newNode(char data, int freq) {
  struct Node* temp = malloc(sizeof(struct Node));
  temp->data = data;
  temp->freq = freq;
  temp->left = temp->right = NULL;
  return temp;
}

// Code to combine two nodes
struct Node* combineNodes(struct Node* left, struct Node* right) {
  struct Node* parent = newNode('$', left->freq + right->freq);
  parent->left = left;
  parent->right = right;
  return parent;
}

// Usage:
struct Node* n1 = newNode('A', 5);
struct Node* n2 = newNode('B', 9);
struct Node* parent = combineNodes(n1, n2);

printf("Parent freq: %d\n", parent->freq);

What is the output of this code?

medium

A. Parent freq: 5

B. Parent freq: 9

C. Compilation error

D. Parent freq: 14

Solution

1. Step 1: Understand node creation and combination

   n1 has freq 5, n2 has freq 9; combineNodes sums frequencies: 5 + 9 = 14.

2. Step 2: Print parent frequency

   parent->freq is 14, so printf outputs "Parent freq: 14".

3. Final Answer:

   Parent freq: 14 -> Option D

4. Quick Check:

   5 + 9 = 14 frequency sum [OK]

Hint: Sum frequencies when combining nodes for parent freq [OK]

Common Mistakes:

• Printing child node frequency instead of parent
• Forgetting to sum frequencies
• Assuming compilation error due to struct usage

5. You have characters with frequencies: X=3, Y=3, Z=3, W=3. Using Huffman Encoding, what is the minimum total number of bits needed to encode the string "XYZWXYZW" (8 characters)?

hard

A. 12 bits

B. 24 bits

C. 16 bits

D. 8 bits

Solution

1. Step 1: Build Huffman tree for equal frequencies

   All characters have equal frequency (3), so Huffman codes will have equal length, typically 2 bits each (since 4 chars need 2 bits minimum).

2. Step 2: Calculate total bits for 8 characters

   Each character uses 2 bits, total bits = 8 * 2 = 16 bits.

3. Step 3: Re-examine options and problem

   Options include 16 and 24 bits. Since each char is 2 bits, total is 16 bits, but 24 bits is 24 bits. The string length is 8, so 8*2=16 bits is correct.

4. Final Answer:

   16 bits -> Option C

5. Quick Check:

   4 chars need 2 bits each, 8 chars total = 16 bits [OK]

Hint: Equal freq chars get equal length codes; multiply length by count [OK]

Common Mistakes:

• Assuming 1 bit per char incorrectly
• Multiplying frequency instead of code length
• Choosing 24 bits thinking 3 bits per char