Huffman Encoding in DSA Rust

Mental Model

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

Analogy: Imagine packing a suitcase where you put small, frequent items in easy-to-reach spots and rare, big items deeper inside to save space.

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 nodes combine smallest frequencies step by step.

Dry Run Walkthrough

Input: characters with frequencies: A:5, B:9, C:12, D:13, E:16, F:45

Goal: Build Huffman tree and assign codes to each character minimizing total bits

Step 1: Pick two smallest nodes A:5 and B:9, combine into new node with freq 14

[14] -> [C:12] -> [D:13] -> [E:16] -> [F:45]
(14 is parent of A and B)

Why: Combining smallest frequencies reduces total code length

Step 2: Pick two smallest nodes C:12 and D:13, combine into new node with freq 25

[14] -> [25] -> [E:16] -> [F:45]
(25 is parent of C and D)

Why: Continue combining smallest nodes to build tree bottom-up

Step 3: Pick two smallest nodes 14 and E:16, combine into new node with freq 30

[25] -> [30] -> [F:45]
(30 is parent of 14 and E)

Why: Merge next smallest nodes to keep tree balanced

Step 4: Pick two smallest nodes 25 and 30, combine into new node with freq 55

[45] -> [55]
(55 is parent of 25 and 30)

Why: Build upper tree levels by combining nodes

Step 5: Pick two remaining nodes 45 and 55, combine into root node with freq 100

[100]
(100 is root, parent of 45 and 55)

Why: Final root node represents total frequency sum

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

Codes:
F:0
C:100
D:101
A:1100
B:1101
E:111

Why: Assign shorter codes to frequent chars by tree depth

Result:

Huffman tree root with freq 100
Codes:
F:0
C:100
D:101
A:1100
B:1101
E:111

Annotated Code

DSA Rust

use std::collections::{BinaryHeap, HashMap};
use std::cmp::Ordering;

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

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

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

fn build_huffman_tree(freq_map: &HashMap<char, usize>) -> Option<Box<Node>> {
    let mut heap = BinaryHeap::new();
    // Create leaf nodes for each character
    for (&ch, &freq) in freq_map {
        heap.push(Node { freq, char_opt: Some(ch), left: None, right: None });
    }

    // Combine nodes until one tree remains
    while heap.len() > 1 {
        let right = heap.pop().unwrap();
        let left = heap.pop().unwrap();
        let merged = Node {
            freq: left.freq + right.freq,
            char_opt: None,
            left: Some(Box::new(left)),
            right: Some(Box::new(right)),
        };
        heap.push(merged);
    }

    heap.pop().map(Box::new)
}

fn generate_codes(node: &Option<Box<Node>>, prefix: String, codes: &mut HashMap<char, String>) {
    if let Some(n) = node {
        if let Some(ch) = n.char_opt {
            codes.insert(ch, prefix);
        } else {
            generate_codes(&n.left, format!("{}0", prefix), codes);
            generate_codes(&n.right, format!("{}1", prefix), codes);
        }
    }
}

fn main() {
    let freq_map = HashMap::from([
        ('A', 5), ('B', 9), ('C', 12), ('D', 13), ('E', 16), ('F', 45)
    ]);

    let tree = build_huffman_tree(&freq_map);
    let mut codes = HashMap::new();
    generate_codes(&tree, String::new(), &mut codes);

    let mut chars: Vec<char> = codes.keys().copied().collect();
    chars.sort();
    for ch in chars {
        println!("{}: {}", ch, codes[&ch]);
    }
}

while heap.len() > 1 {

combine two smallest nodes repeatedly to build tree

let left = heap.pop().unwrap();

pop smallest node from heap

let right = heap.pop().unwrap();

pop next smallest node from heap

let merged = Node { freq: left.freq + right.freq, ... };

create new parent node with combined frequency

heap.push(merged);

push merged node back to heap to continue building tree

if let Some(ch) = n.char_opt { codes.insert(ch, prefix); } else { ... }

assign code to leaf node or recurse for internal nodes

Output

A: 1100

B: 1101

C: 100

D: 101

E: 111

F: 0

Complexity Analysis

Time: O(n log n) because we insert and remove nodes from a heap n times where n is number of unique chars

Space: O(n) for storing nodes and codes for each unique character

vs Alternative: Compared to fixed-length codes, Huffman reduces average code length by using variable-length codes based on frequency

Edge Cases

empty frequency map

returns None, no tree built

DSA Rust

heap.pop().map(Box::new)

single character frequency

tree with single node, code is empty string

DSA Rust

while heap.len() > 1

When to Use This Pattern

When you need to compress data by assigning shorter codes to frequent items, reach for Huffman Encoding because it builds an optimal prefix code tree.

Common Mistakes

Mistake: Not reversing the order in heap comparison causing max-heap instead of min-heap
Fix: Reverse comparison in Ord implementation to get min-heap behavior

Mistake: Assigning codes only at root or not traversing tree correctly
Fix: Use recursive traversal assigning 0 to left edges and 1 to right edges

Summary

Builds a tree to assign shorter binary codes to frequent characters for compression.

Use when you want to compress data efficiently by frequency of characters.

Combine smallest frequency nodes step-by-step to build a prefix-free binary tree.

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