Huffman Encoding in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Huffman Encoding?

Huffman Encoding is a way to compress data by using shorter codes for common letters and longer codes for rare letters. It builds a tree to assign these codes so the total size is smaller.

beginner

How does Huffman Encoding decide the code length for each character?

It gives shorter codes to characters that appear more often and longer codes to characters that appear less often, making the overall message smaller.

intermediate

What data structure is mainly used in Huffman Encoding to build the codes?

A binary tree called the Huffman tree is used. Each leaf node is a character, and the path from root to leaf gives the character's code.

intermediate

In Huffman Encoding, what does combining two nodes with the smallest frequencies achieve?

It creates a new node with their combined frequency, helping build the tree from bottom up so that less frequent characters end up deeper with longer codes.

advanced

Why is Huffman Encoding considered a prefix code?

Because no code is the start of another code, so decoding is easy and unambiguous by reading bits until a full code matches.

What is the first step in building a Huffman tree?

A Calculate frequency of each character

B Sort characters alphabetically

C Assign random codes to characters

D Build a balanced binary tree

The first step is to count how often each character appears to know their frequencies.

In Huffman Encoding, what does a leaf node represent?

A A combined frequency of two characters

B A character with its frequency

C An internal node with no character

D The root of the tree

Leaf nodes represent actual characters and their frequencies.

Why are shorter codes assigned to more frequent characters in Huffman Encoding?

A To make the encoded message smaller

B To make decoding faster

C To balance the tree

D To confuse attackers

Shorter codes for frequent characters reduce the total bits needed, compressing the data.

What property ensures Huffman codes can be decoded without ambiguity?

A Suffix codes

B Fixed-length codes

C Random codes

D Prefix-free codes

Huffman codes are prefix-free, meaning no code is the start of another, so decoding is clear.

Which data structure is commonly used to pick the two smallest frequency nodes during Huffman tree construction?

A Queue

B Stack

C Min-heap (priority queue)

D Hash map

A min-heap helps efficiently find and remove the two smallest frequency nodes.

Explain how Huffman Encoding compresses data using a tree structure.

Think about how characters with different frequencies get different code lengths.

Describe why Huffman codes are prefix-free and how this helps in decoding.

Consider how you can tell where one code ends and another begins.

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