Huffman Encoding in DSA Python

Mental Model

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

Analogy: Imagine you have a box of colored pencils where you use some colors a lot and others rarely. You label the common colors with short names and rare colors with longer names to write faster.

Characters with 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 after combining two smallest:
       *
      / \
   [a:5] [b:9]

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

Dry Run Walkthrough

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

Goal: build a Huffman tree and generate codes for each character

Step 1: combine nodes with smallest frequencies a:5 and b:9 into new node *:14

[*:14]  [c:12]  [d:13]  [e:16]  [f:45]
Tree:
       *
      / \
   [a:5] [b:9]

Why: combining smallest frequencies reduces total weighted path length

Step 2: combine nodes with smallest frequencies c:12 and d:13 into new node *:25

[*:14]  [*:25]  [e:16]  [f:45]
Tree:
       *:25
      /    \
   [c:12]  [d:13]

Why: next smallest nodes combined to build tree bottom-up

Step 3: combine nodes with smallest frequencies *:14 and e:16 into new node *:30

[*:25]  [*:30]  [f:45]
Tree:
       *:30
      /    \
   *:14    [e:16]
  /    \
[a:5] [b:9]

Why: continue combining smallest nodes to build tree

Step 4: combine nodes with smallest frequencies *:25 and *:30 into new node *:55

[*:55]  [f:45]
Tree:
       *:55
      /    \
   *:25    *:30
  /    \   /    \
[c:12][d:13][*:14][e:16]
           /  \
        [a:5][b:9]

Why: merge larger combined nodes to approach full tree

Step 5: combine remaining nodes *:55 and f:45 into root node *:100

[*:100]
Tree:
        *:100
       /     \
    *:55     [f:45]
    /    \
 *:25    *:30
/   \   /    \
[c:12][d:13][*:14][e:16]
                  /  \
               [a:5][b:9]

Why: final combination forms full Huffman tree

Step 6: assign codes by traversing tree: left edge adds '0', right edge adds '1'

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

Why: codes are generated by path from root to leaves

Result:

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

Annotated Code

DSA Python

import heapq

class Node:
    def __init__(self, freq, char=None, left=None, right=None):
        self.freq = freq
        self.char = char
        self.left = left
        self.right = right
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(freq_map):
    heap = [Node(freq, char) for char, freq in freq_map.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        left = heapq.heappop(heap)  # pop smallest freq node
        right = heapq.heappop(heap) # pop next smallest
        merged = Node(left.freq + right.freq, None, left, right)  # merge nodes
        heapq.heappush(heap, merged)  # push merged node back

    return heap[0] if heap else None

def generate_codes(node, prefix='', code_map=None):
    if code_map is None:
        code_map = {}
    if node is None:
        return code_map
    if node.char is not None:
        code_map[node.char] = prefix  # leaf node: assign code
    else:
        generate_codes(node.left, prefix + '0', code_map)  # left edge adds '0'
        generate_codes(node.right, prefix + '1', code_map) # right edge adds '1'
    return code_map

# Driver code
freq_map = {'a':5, 'b':9, 'c':12, 'd':13, 'e':16, 'f':45}
root = build_huffman_tree(freq_map)
codes = generate_codes(root)
for char in sorted(codes):
    print(f"{char}: {codes[char]}")

left = heapq.heappop(heap) # pop smallest freq node

extract smallest frequency node to combine

right = heapq.heappop(heap) # pop next smallest

extract next smallest frequency node

merged = Node(left.freq + right.freq, None, left, right) # merge nodes

create new internal node with combined frequency

heapq.heappush(heap, merged) # push merged node back

insert merged node back to heap for further processing

if node.char is not None: code_map[node.char] = prefix # leaf node: assign code

assign code to leaf character

generate_codes(node.left, prefix + '0', code_map) # left edge adds '0'

traverse left subtree adding '0' to code

generate_codes(node.right, prefix + '1', code_map) # right edge adds '1'

traverse right subtree adding '1' to code

Output

a: 1100

b: 1101

c: 100

d: 101

e: 111

f: 0

Complexity Analysis

Time: O(n log n) because building the heap and merging nodes requires log n operations for each of the n characters

Space: O(n) because we store nodes and codes for each character

vs Alternative: Compared to fixed-length encoding which uses same length codes, Huffman encoding reduces average code length and saves space but requires extra tree building time

Edge Cases

empty frequency map

returns None and no codes generated

DSA Python

return heap[0] if heap else None

single character frequency

code assigned as empty string or '0' since only one character

DSA Python

if node.char is not None:
        code_map[node.char] = prefix

all characters have same frequency

tree built normally, codes assigned but may not be shortest possible

DSA Python

heapq operations handle equal frequencies correctly

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 using a priority queue to always combine smallest frequency nodes first
Fix: Use a min-heap (priority queue) to pick two smallest nodes at each step

Mistake: Assigning codes incorrectly by mixing left and right edges
Fix: Consistently assign '0' to left edges and '1' to right edges during tree traversal

Summary

Builds a tree to assign shorter codes to frequent characters and longer codes to rare ones for compression.

Use when you want to compress data efficiently by minimizing average code length.

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

Practice

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

easy

A. To encrypt data for security

B. To assign equal length codes to all characters

C. To assign shorter codes to more frequent characters

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding aims to reduce the total bits used by assigning 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 B, C, and D do not describe Huffman Encoding's purpose.

3. Final Answer:

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

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 Huffman with encryption
• Assuming it sorts characters alphabetically

2. Which Python data structure is commonly used to build the Huffman tree efficiently?

easy

A. List

B. Heap (priority queue)

C. Dictionary

D. Queue

Solution

1. Step 1: Identify data structure for minimum frequency extraction

   Huffman tree construction repeatedly extracts two nodes with the smallest frequencies.

2. Step 2: Choose data structure supporting efficient min extraction

   A heap (priority queue) allows quick access to the smallest element, making it ideal.

3. Final Answer:

   Heap (priority queue) -> Option B

4. Quick Check:

   Min extraction = heap (priority queue) [OK]

Hint: Use a heap for fast smallest frequency access [OK]

Common Mistakes:

• Using a list without sorting repeatedly
• Choosing a queue which is FIFO, not min-based
• Assuming dictionary stores order

3. What is the output of the following Python code snippet that builds a Huffman tree for characters with frequencies {'a': 5, 'b': 9, 'c': 12}?

import heapq
freq = [('a', 5), ('b', 9), ('c', 12)]
heap = [(f, ch) for ch, f in freq]
heapq.heapify(heap)
while len(heap) > 1:
    f1, ch1 = heapq.heappop(heap)
    f2, ch2 = heapq.heappop(heap)
    heapq.heappush(heap, (f1 + f2, ch1 + ch2))
print(heap[0])

medium

A. (26, 'cab')

B. (26, 'abc')

C. (26, 'cba')

D. (26, 'bac')

Solution

1. Step 1: Initialize heap with frequencies

   Heap contains (5,'a'), (9,'b'), (12,'c'). After heapify, smallest frequency is (5,'a').

2. Step 2: Combine two smallest nodes repeatedly

   Pop (5,'a') and (9,'b'), combine to (14,'ab'), push back. Heap now has (12,'c') and (14,'ab'). Pop (12,'c') and (14,'ab') and combine to (26,'cab').

3. Final Answer:

   (26, 'cab') -> Option A

4. Quick Check:

   Sum freq = 5+9+12 = 26, combined chars 'cab' [OK]

Hint: Sum frequencies and combine chars in order popped [OK]

Common Mistakes:

• Mixing character order in combined string
• Adding frequencies incorrectly
• Not heapifying before popping

4. Identify the error in this Huffman tree building code snippet:

import heapq
freq = {'a': 3, 'b': 2, 'c': 6}
heap = []
for ch, f in freq.items():
    heapq.heappush(heap, (ch, f))
while len(heap) > 1:
    f1, ch1 = heapq.heappop(heap)
    f2, ch2 = heapq.heappop(heap)
    heapq.heappush(heap, (f1 + f2, ch1 + ch2))
print(heap[0])

medium

A. Incorrect loop condition in while

B. Heap elements pushed with frequency first, character second

C. Using heappush instead of heapify

D. Heap elements pushed with character first, frequency second

Solution

1. Step 1: Check heap element structure

   Heap elements must be tuples with frequency first for correct min-heap behavior.

2. Step 2: Identify error in heappush order

   Code pushes (ch, f) instead of (f, ch), so heap compares characters, not frequencies.

3. Final Answer:

   Heap elements pushed with character first, frequency second -> Option D

4. Quick Check:

   Frequency must be first in heap tuple [OK]

Hint: Push (frequency, character) tuples to heap [OK]

Common Mistakes:

• Swapping frequency and character order
• Not using heapify for initial heap
• Wrong while loop condition

5. Given the frequencies {'x': 4, 'y': 7, 'z': 8, 'w': 15}, what is the Huffman code for character 'w' after building the tree? Assume left edge is '0' and right edge is '1'.

hard

A. '0'

B. '11'

C. '1'

D. '10'

Solution

1. Step 1: Build Huffman tree with given frequencies

   Initial heap: (4,'x'), (7,'y'), (8,'z'), (15,'w'). Combine smallest: (4,'x') + (7,'y') = (11,'xy'). Heap now (8,'z'), (11,'xy'), (15,'w'). Combine (8,'z') + (11,'xy') = (19,'zxy'). Heap now (15,'w'), (19,'zxy'). Combine (15,'w') + (19,'zxy') = (34,'wzxy').

2. Step 2: Assign codes from root to leaves

   Root splits into left child (15,'w') and right child (19,'zxy'). 'w' is left child, so code is '0'.

3. Final Answer:

   '0' -> Option A

4. Quick Check:

   'w' is left child of root = '0' [OK]

Hint: Largest freq often gets shortest code at root edge [OK]

Common Mistakes:

• Assigning 'w' code as '1' instead of '0'
• Confusing left/right edges
• Not building tree stepwise