Huffman Encoding in DSA Go - Execution Trace

Concept Flow - Huffman Encoding

Count frequencies of chars

↓

Create leaf nodes for each char

↓

Build min-heap from leaf nodes

↓

While heap size > 1

↓

Extract two smallest nodes

↓

Create new internal node with these two as children

↓

Insert new node back into heap

↓

Heap has one node -> root of Huffman Tree

↓

Traverse tree to assign codes

↓

Encode input using codes

The flow counts character frequencies, builds a tree by combining smallest nodes, then assigns codes by traversing the tree.

Execution Sample

DSA Go

freq := map[rune]int{'a':5, 'b':9, 'c':12, 'd':13, 'e':16, 'f':45}
heap := buildMinHeap(freq)
for heap.size() > 1 {
  left := heap.extractMin()
  right := heap.extractMin()
  merged := newNode(left.freq + right.freq, left, right)
  heap.insert(merged)
}
codes := generateCodes(heap.extractMin(), "")

This code builds a Huffman tree from character frequencies and generates codes.

Execution Table

Step	Heap State (freqs)	Action	New Node Created	Heap After Insertion
1	[5,9,12,13,16,45]	Extract 5 and 9	Node(freq=14)	[12,13,14,16,45]
2	[12,13,14,16,45]	Extract 12 and 13	Node(freq=25)	[14,16,25,45]
3	[14,16,25,45]	Extract 14 and 16	Node(freq=30)	[25,30,45]
4	[25,30,45]	Extract 25 and 30	Node(freq=55)	[45,55]
5	[45,55]	Extract 45 and 55	Node(freq=100)	[100]
6	[100]	Only one node left - root	None	[100]

💡 Heap size is 1, so the Huffman tree is complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
heap	[5,9,12,13,16,45]	[12,13,14,16,45]	[14,16,25,45]	[25,30,45]	[45,55]	[100]	[100]
left.freq	-	5	12	14	25	45	-
right.freq	-	9	13	16	30	55	-
merged.freq	-	14	25	30	55	100	-

Key Moments - 3 Insights

Why do we always extract two smallest nodes from the heap?

Because combining the two smallest frequencies ensures the overall code length is minimized, as shown in execution_table steps 1-5 where smallest nodes are merged.

What happens when the heap size becomes 1?

At step 6 in execution_table, when heap size is 1, it means the Huffman tree is fully built with one root node.

Why do we insert the merged node back into the heap?

Inserting the merged node back keeps the heap updated with combined frequencies, allowing the next smallest pairs to be merged, as seen after each step in the heap state.

Visual Quiz - 3 Questions

Look at the execution_table, what is the heap state after step 3?

A [25,30,45]

B [14,16,25,45]

C [12,13,14,16,45]

D [45,55]

💡 Hint

Check the 'Heap After Insertion' column for step 3 in execution_table.

At which step does the merged node with frequency 55 get created?

A Step 5

B Step 3

C Step 4

D Step 2

💡 Hint

Look at the 'New Node Created' column in execution_table for frequency 55.

If the frequency of 'f' was 50 instead of 45, how would the first step's heap state change?

A [12,13,14,16,50]

B [5,9,12,13,16,50]

C [5,9,12,13,16,45]

D [12,13,14,16,45]

💡 Hint

Check the initial heap state in execution_table step 1 and consider the frequency change.

Concept Snapshot

Huffman Encoding builds a tree from character frequencies.
Use a min-heap to combine two smallest nodes repeatedly.
Create new internal nodes with combined frequency.
Stop when one node remains - the root.
Traverse tree to assign binary codes.
Encode data using these codes for compression.

Full Transcript

Huffman Encoding starts by counting how often each character appears. Then, it creates leaf nodes for each character with their frequencies. These nodes go into a min-heap, which always lets us pick the two smallest frequency nodes. We remove these two smallest nodes, combine them into a new node with their total frequency, and put this new node back into the heap. We repeat this until only one node remains, which becomes the root of the Huffman tree. Finally, we traverse this tree to assign binary codes to each character. This process ensures the most frequent characters get shorter codes, making the overall data smaller when encoded.

Practice

1. What is the main goal 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 purpose

   Huffman Encoding compresses data by using variable-length codes based on character frequency.

2. Step 2: Identify code assignment rule

   More frequent characters get shorter codes to reduce overall data size.

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 all codes have same length
• Confusing compression with encryption
• Assuming alphabetical order affects codes

2. Which of the following Go code snippets correctly declares a priority queue for Huffman nodes using container/heap?

easy

A. type HuffmanNode struct {char string; freq float64}; var pq []HuffmanNode

B. var pq []int = make([]int, 0)

C. type HuffmanNode struct {char rune; freq int}; type PriorityQueue []*HuffmanNode

D. var pq map[rune]int = make(map[rune]int)

Solution

1. Step 1: Identify correct struct for Huffman node

   HuffmanNode should have a character (rune) and frequency (int).

2. Step 2: Check priority queue declaration

   PriorityQueue should be a slice of pointers to HuffmanNode for heap operations.

3. Final Answer:

   type HuffmanNode struct {char rune; freq int}; type PriorityQueue []*HuffmanNode -> Option C

4. Quick Check:

   Priority queue = slice of HuffmanNode pointers [OK]

Hint: Use slice of pointers for priority queue [OK]

Common Mistakes:

• Using map instead of slice for priority queue
• Using wrong data types for char or freq
• Declaring slice of values instead of pointers

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

medium

A. 10

B. 00

C. 111

D. 110

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 '10' (left-right).

3. Final Answer:

   10 -> Option A

4. Quick Check:

   'a' = code '10' [OK]

Hint: Lowest freq chars get codes starting with 1 or 0 depending on tree [OK]

Common Mistakes:

• Assigning longer codes to lowest freq chars
• Mixing up left and right branches
• Ignoring tree structure when assigning codes

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

func buildTree(freq map[rune]int) *Node {
  pq := &PriorityQueue{}
  heap.Init(pq)
  for c, f := range freq {
    heap.Push(pq, &Node{char: c, freq: f})
  }
  for pq.Len() > 1 {
    left := heap.Pop(pq).(*Node)
    right := heap.Pop(pq).(*Node)
    merged := &Node{freq: left.freq + right.freq, left: left, right: right}
    heap.Push(pq, merged)
  }
  return heap.Pop(pq).(*Node)
}

medium

A. PriorityQueue must implement heap.Interface methods

B. freq map keys should be string, not rune

C. heap.Init should be called after pushing elements

D. Cannot push pointers to heap

Solution

1. Step 1: Check PriorityQueue usage with heap

   Go's heap requires the PriorityQueue type to implement heap.Interface methods Len, Less, Swap, Push, and Pop.

2. Step 2: Identify missing implementation

   If PriorityQueue does not implement these methods, heap.Init and heap.Push will cause runtime errors.

3. Final Answer:

   PriorityQueue must implement heap.Interface methods -> Option A

4. Quick Check:

   heap.Interface implementation required [OK]

Hint: Always implement heap.Interface for priority queues [OK]

Common Mistakes:

• Using wrong key type in freq map
• Calling heap.Init too early or late
• Trying to push non-pointer values

5. You have a string "aaabbc" and want to encode it using Huffman Encoding. Which of the following steps correctly describes how to build the Huffman tree and generate codes?

hard

A. Sort characters alphabetically, assign fixed-length codes, encode string

B. Count frequencies, build min-heap, merge nodes until one tree, assign codes from tree

C. Assign random codes to characters, then compress string

D. Use frequency to assign codes but skip building tree

Solution

1. Step 1: Count character frequencies

   For "aaabbc", frequencies are: 'a':3, 'b':2, 'c':1.

2. Step 2: Build min-heap and merge nodes

   Create nodes for each char, push into min-heap, merge two smallest nodes repeatedly until one tree remains.

3. Step 3: Assign codes from the tree

   Traverse tree assigning '0' for left and '1' for right edges to generate prefix codes.

4. Final Answer:

   Count frequencies, build min-heap, merge nodes until one tree, assign codes from tree -> Option B

5. Quick Check:

   Huffman = freq count + min-heap + merge + code assign [OK]

Hint: Follow frequency -> min-heap -> merge -> code assign steps [OK]

Common Mistakes:

• Skipping tree building step
• Assigning fixed-length codes ignoring frequency
• Using random codes without structure