Huffman Encoding in DSA Rust - Execution Trace

Concept Flow - Huffman Encoding

Count frequencies of chars

↓

Create leaf nodes for each char

↓

Build min-heap of nodes

↓

While heap size > 1

↓

Pop two smallest nodes

↓

Create new 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

Huffman Encoding builds a tree from character frequencies to assign short codes to frequent chars, compressing data.

Execution Sample

DSA Rust

let text = "abbccc";
let freq = count_frequencies(text);
let tree = build_huffman_tree(freq);
let codes = generate_codes(&tree);
let encoded = encode_text(text, &codes);

This code counts character frequencies, builds the Huffman tree, generates codes, and encodes the text.

Execution Table

Step	Action	Heap State (nodes with freq)	Tree Nodes Created	Notes
1	Count frequencies	{"a":1, "b":2, "c":3}	None	Frequencies counted from text 'abbccc'
2	Create leaf nodes	[a:1, b:2, c:3]	Leaf nodes for a,b,c	Each char becomes a leaf node
3	Build min-heap	[a:1, b:2, c:3]	None	Min-heap built from leaf nodes
4	Pop two smallest	[c:3]	Nodes popped: a:1, b:2	Smallest two nodes removed
5	Create new node	[c:3, ab:3]	New node ab:3 with children a,b	Combined nodes a and b
6	Insert new node	[c:3, ab:3]	None	New node inserted back
7	Pop two smallest	[]	Nodes popped: c:3, ab:3	Two smallest nodes popped
8	Create new node	[abc:6]	New node abc:6 with children ab, c	Root node created
9	Insert new node	[abc:6]	None	Root node inserted
10	Heap size 1	Heap has one node	Tree complete	Huffman tree built
11	Generate codes	N/A	Codes: a=10, b=11, c=0	Traverse tree to assign codes
12	Encode text	N/A	Encoded: 10 11 11 0 0 0	Text encoded using codes
13	End	N/A	Encoding complete	Process finished

💡 Heap size is 1, tree is complete, encoding done

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	Final
freq	{}	{"a":1, "b":2, "c":3}	{"a":1, "b":2, "c":3}	{"a":1, "b":2, "c":3}	{"a":1, "b":2, "c":3}
heap	[]	[a:1, b:2, c:3]	[c:3, ab:3]	[abc:6]	[abc:6]
tree	None	Leaf nodes a,b,c	Partial tree with ab node	Full tree abc root	Full tree abc root
codes	{}	{}	{}	{"a":"10", "b":"11", "c":"0"}	{"a":"10", "b":"11", "c":"0"}
encoded	""	""	""	""	"101111000"

Key Moments - 3 Insights

Why do we combine the two smallest nodes each time?

Combining the two smallest nodes (see steps 4-8) ensures the tree gives shorter codes to frequent chars, which is key to compression.

How do we know when the Huffman tree is complete?

When the heap has only one node left (step 10), that node is the root of the complete Huffman tree.

Why does 'c' get code '0' while 'a' and 'b' get longer codes?

Because 'c' has the highest frequency (3), it stays closer to the root, getting a shorter code (step 11). Less frequent chars get longer codes.

Visual Quiz - 3 Questions

Look at the execution table at step 5. What nodes were combined to create the new node?

A Nodes with frequencies 1 and 2

B Nodes with frequencies 2 and 3

C Nodes with frequencies 3 and 3

D Nodes with frequencies 1 and 3

💡 Hint

Check the 'Tree Nodes Created' and 'Heap State' columns at step 5 in the execution table.

At which step does the heap size become 1, indicating the tree is complete?

A Step 8

B Step 6

C Step 10

D Step 12

💡 Hint

Look for the step where 'Heap size 1' and 'Tree complete' appear in the execution table.

According to the variable tracker, what is the encoded string after all steps?

A "111000101"

B "101111000"

C "000111101"

D "110100011"

💡 Hint

Check the 'encoded' variable's final value in the variable tracker section.

Concept Snapshot

Huffman Encoding:
- Count char frequencies
- Build min-heap of leaf nodes
- Combine two smallest nodes repeatedly
- Resulting single node is tree root
- Traverse tree to assign binary codes
- Encode text using these codes
- Frequent chars get shorter codes
- Used for lossless data compression

Full Transcript

Huffman Encoding compresses data by assigning shorter binary codes to frequent characters. First, count how often each character appears. Then create leaf nodes for each character and build a min-heap. Repeatedly remove the two smallest nodes, combine them into a new node with their sum frequency, and insert it back. When only one node remains, it is the root of the Huffman tree. Traverse this tree to assign codes: left edges add '0', right edges add '1'. Finally, encode the original text by replacing each character with its code. This process ensures efficient compression by giving shorter codes to more frequent characters.

Practice

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

easy

A. To assign shorter codes to more frequent characters

B. To assign equal length codes to all characters

C. To encrypt data for security

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding compresses data 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; others describe different concepts.

3. Final Answer:

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

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 Rust data structure is best suited to implement the priority queue needed for Huffman Encoding?

easy

A. BinaryHeap<T>

B. HashMap

C. Vec<T>

D. LinkedList<T>

Solution

1. Step 1: Identify priority queue requirement

   Huffman Encoding needs a structure to get the smallest frequency element quickly.

2. Step 2: Match Rust structures to priority queue

   BinaryHeap<T> is Rust's built-in priority queue supporting efficient min/max operations.

3. Final Answer:

   BinaryHeap<T> -> Option A

4. Quick Check:

   Priority queue = BinaryHeap in Rust [OK]

Hint: Use BinaryHeap for priority queues in Rust [OK]

Common Mistakes:

• Using Vec without sorting for priority queue
• Choosing HashMap which is for key-value pairs
• Using LinkedList which is inefficient here

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

use std::collections::BinaryHeap;

#[derive(Eq, PartialEq)]
struct Node {
    freq: usize,
    char_opt: Option<char>,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.freq.cmp(&self.freq) // min-heap behavior
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(Node { freq: 5, char_opt: Some('a') });
    heap.push(Node { freq: 9, char_opt: Some('b') });
    heap.push(Node { freq: 12, char_opt: Some('c') });

    let first = heap.pop().unwrap();
    let second = heap.pop().unwrap();

    println!("{} {}", first.freq, second.freq);
}

medium

A. 9 5

B. 12 9

C. 5 9

D. 5 12

Solution

1. Step 1: Understand BinaryHeap with custom Ord

   The cmp reverses order to make a min-heap by frequency, so pop() returns smallest freq first.

2. Step 2: Pop two smallest frequencies

   Frequencies are 5, 9, 12. First pop returns 5, second pop returns 9.

3. Final Answer:

   5 9 -> Option C

4. Quick Check:

   Min-heap pops smallest first = 5 9 [OK]

Hint: Custom Ord reverses cmp for min-heap pop order [OK]

Common Mistakes:

• Assuming BinaryHeap is max-heap by default
• Mixing order of popped elements
• Ignoring custom Ord implementation

4. Identify the bug in this Rust code snippet that tries to build a Huffman tree node by combining two nodes:

struct Node {
    freq: usize,
    left: Option,
    right: Option,
}

fn combine_nodes(left: Node, right: Node) -> Node {
    Node {
        freq: left.freq + right.freq,
        left: Some(Box::new(left)),
        right: Some(Box::new(right)),
    }
}

fn main() {
    let n1 = Node { freq: 3, left: None, right: None };
    let n2 = Node { freq: 4, left: None, right: None };
    let parent = combine_nodes(n1, n2);
    println!("Parent freq: {}", parent.freq);
}

medium

A. Cannot use Box::new with struct Node

B. Missing lifetime annotations for Box<Node>

C. Function should take references, not owned Nodes

D. No bug, code compiles and runs correctly

Solution

1. Step 1: Check ownership and Box usage

   Function takes owned Nodes and boxes them correctly for left and right fields.

2. Step 2: Verify code compiles and runs

   Code compiles and prints combined frequency without errors.

3. Final Answer:

   No bug, code compiles and runs correctly -> Option D

4. Quick Check:

   Ownership and Box usage correct = no bug [OK]

Hint: Owned nodes boxed correctly means no bug here [OK]

Common Mistakes:

• Assuming lifetime needed for Box<Node> here
• Thinking references required instead of ownership
• Believing Box::new cannot wrap structs

5. Given character frequencies {'x': 7, 'y': 3, 'z': 2, 'w': 6}, which of the following Huffman codes is valid and optimal?

hard

A. x: 11, y: 10, z: 0, w: 1

B. x: 0, y: 10, z: 110, w: 111

C. x: 10, y: 0, z: 111, w: 110

D. x: 0, y: 1, z: 10, w: 11

Solution

1. Step 1: Order characters by frequency

   Frequencies: z=2, y=3, w=6, x=7. Huffman assigns shortest codes to highest freq.

2. Step 2: Check code lengths and prefix property

   x: 0, y: 10, z: 110, w: 111 assigns shortest code '0' to x (freq 7), longer codes to lower freq chars, and codes are prefix-free.

3. Final Answer:

   x: 0, y: 10, z: 110, w: 111 -> Option B

4. Quick Check:

   Shortest code to highest freq = x: 0, y: 10, z: 110, w: 111 [OK]

Hint: Shortest code goes to highest frequency char [OK]

Common Mistakes:

• Assigning short codes to low frequency chars
• Ignoring prefix-free property
• Confusing code length order