Huffman Encoding in DSA Java

Mental Model

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

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

Frequency Table:
A:5 B:9 C:12 D:13 E:16 F:45

Huffman Tree (partial):
        [100]
       /     \
    [45]     [55]
   (F)      /    \
          [25]   [30]
         /   \   /  \
       (C)  (D)(A)  [14]
                    /  \
                  (B)  (E)

Dry Run Walkthrough

Input: string: 'ABBCCCDDDDEEEEEFFFFFFF' (characters with frequencies: A=1, B=2, C=3, D=4, E=5, F=7)

Goal: Build Huffman tree and generate codes for each character to minimize total bits used

Step 1: Create leaf nodes for each character with their frequencies

[A:1], [B:2], [C:3], [D:4], [E:5], [F:7]

Why: We start with all characters as separate nodes to build the tree

Step 2: Pick two nodes with smallest frequencies (A:1, B:2), merge into new node with freq 3

[C:3], [D:4], [E:5], [F:7], [AB:3]

Why: Combine smallest frequencies to build tree bottom-up

Step 3: Pick two smallest nodes (C:3, AB:3), merge into new node with freq 6

[D:4], [E:5], [F:7], [CAB:6]

Why: Continue merging smallest nodes to build tree

Step 4: Pick two smallest nodes (D:4, E:5), merge into new node with freq 9

[F:7], [CAB:6], [DE:9]

Why: Keep merging until one node remains

Step 5: Pick two smallest nodes (F:7, CAB:6), merge into new node with freq 13

[DE:9], [FCAB:13]

Why: Merge next smallest nodes

Step 6: Merge last two nodes (DE:9, FCAB:13) into root node with freq 22

[Root:22]

Why: Final merge creates the Huffman tree root

Step 7: Assign codes by traversing tree: left edge adds '0', right edge adds '1'

Codes: A=1010, B=1011, C=100, D=00, E=01, F=11

Why: Assign shorter codes to frequent characters

Result:

Huffman Codes:
A:1010
B:1011
C:100
D:00
E:01
F:11

Annotated Code

DSA Java

import java.util.*;

class HuffmanNode implements Comparable<HuffmanNode> {
    char ch;
    int freq;
    HuffmanNode left, right;

    HuffmanNode(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
    }

    public int compareTo(HuffmanNode other) {
        return this.freq - other.freq;
    }
}

public class HuffmanEncoding {

    public static Map<Character, String> buildHuffmanTree(Map<Character, Integer> freqMap) {
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();

        // Create leaf nodes for each character
        for (var entry : freqMap.entrySet()) {
            pq.add(new HuffmanNode(entry.getKey(), entry.getValue()));
        }

        // Build the tree
        while (pq.size() > 1) {
            HuffmanNode left = pq.poll(); // smallest freq
            HuffmanNode right = pq.poll(); // next smallest freq

            HuffmanNode merged = new HuffmanNode('\0', left.freq + right.freq);
            merged.left = left;
            merged.right = right;

            pq.add(merged);
        }

        HuffmanNode root = pq.poll();
        Map<Character, String> codes = new HashMap<>();
        buildCodes(root, "", codes);
        return codes;
    }

    private static void buildCodes(HuffmanNode node, String code, Map<Character, String> codes) {
        if (node == null) return;

        if (node.left == null && node.right == null) {
            codes.put(node.ch, code);
            return;
        }

        buildCodes(node.left, code + "0", codes); // left edge adds '0'
        buildCodes(node.right, code + "1", codes); // right edge adds '1'
    }

    public static void main(String[] args) {
        String text = "ABBCCCDDDDEEEEEFFFFFFF";
        Map<Character, Integer> freqMap = new HashMap<>();

        // Count frequencies
        for (char ch : text.toCharArray()) {
            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
        }

        Map<Character, String> codes = buildHuffmanTree(freqMap);

        // Print codes
        for (char ch : freqMap.keySet()) {
            System.out.println(ch + ":" + codes.get(ch));
        }
    }
}

for (var entry : freqMap.entrySet()) { pq.add(new HuffmanNode(entry.getKey(), entry.getValue())); }

Create leaf nodes for each character with frequency

while (pq.size() > 1) { HuffmanNode left = pq.poll(); HuffmanNode right = pq.poll(); HuffmanNode merged = new HuffmanNode('\0', left.freq + right.freq); merged.left = left; merged.right = right; pq.add(merged); }

Merge two smallest nodes repeatedly to build Huffman tree

buildCodes(root, "", codes);

Traverse tree to assign binary codes to characters

if (node.left == null && node.right == null) { codes.put(node.ch, code); return; }

Assign code to leaf node character

buildCodes(node.left, code + "0", codes);

Add '0' for left edge in code

buildCodes(node.right, code + "1", codes);

Add '1' for right edge in code

Output

A:1010

B:1011

C:100

D:00

E:01

F:11

Complexity Analysis

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

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

vs Alternative: Compared to fixed-length encoding which uses same bits per character, Huffman reduces average bits by assigning shorter codes to frequent characters

Edge Cases

Empty input string

Frequency map is empty, so no tree is built and codes map is empty

DSA Java

for (var entry : freqMap.entrySet()) { pq.add(new HuffmanNode(entry.getKey(), entry.getValue())); }

Input string with one unique character

Tree has single node, code assigned is empty string

DSA Java

while (pq.size() > 1) { ... }

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 merging the two smallest frequency nodes first
Fix: Use a priority queue to always pick two nodes with smallest frequencies

Mistake: Assigning codes without ensuring prefix property
Fix: Build codes by traversing the tree, adding '0' for left and '1' for right edges

Summary

It builds a tree to assign shorter binary codes to frequent characters and longer codes to rare ones.

Use it when you want to compress data efficiently by minimizing average bits per character.

The key insight is merging 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 sort characters alphabetically

B. To assign shorter codes to more frequent characters

C. To encrypt data for security

D. To assign equal length codes to all characters

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 goal

   Only To assign shorter codes to more frequent characters matches this goal. Options A, B, and C do not describe Huffman Encoding correctly.

3. Final Answer:

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

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

Hint: Remember: frequent chars get shorter codes [OK]

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing Huffman with encryption
• Assuming it sorts characters alphabetically

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

easy

A. PriorityQueue

B. HashMap

C. ArrayList

D. Stack

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: Match data structure to this need

   A PriorityQueue efficiently provides the smallest element each time, making it ideal for this task.

3. Final Answer:

   PriorityQueue -> Option A

4. Quick Check:

   Minimum extraction = PriorityQueue [OK]

Hint: Use PriorityQueue for smallest frequency extraction [OK]

Common Mistakes:

• Using ArrayList which is not efficient for min extraction
• Choosing HashMap which stores key-value pairs, not order
• Selecting Stack which is LIFO, not suitable here

3. What is the output Huffman code for characters given frequencies: A=5, B=9, C=12, D=13, E=16, F=45? (Assuming standard Huffman algorithm)

medium

A. A: 111, B: 110, C: 101, D: 100, E: 0, F: 11

B. A: 0, B: 111, C: 110, D: 10, E: 101, F: 100

C. A: 100, B: 101, C: 110, D: 111, E: 0, F: 11

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

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies stepwise: (A=5, B=9) -> 14, then combine with C=12, etc., building tree with F=45 as root's child.

2. Step 2: Assign codes from tree paths

   F gets shortest code '0' (highest freq). A and B get longer codes starting with '1100' and '1101' respectively.

3. Final Answer:

   A: 1100, B: 1101, C: 100, D: 101, E: 111, F: 0 -> Option D

4. Quick Check:

   Lowest freq get longest codes = A: 1100, B: 1101, C: 100, D: 101, E: 111, F: 0 [OK]

Hint: Lowest freq get longest codes, highest freq shortest [OK]

Common Mistakes:

• Assigning shortest codes to low frequency chars
• Mixing code assignments without tree structure
• Ignoring frequency order in code lengths

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

PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node('a', 5));
pq.add(new Node('b', 9));
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node(null, left.freq + right.freq);
parent.left = left;
parent.right = right;
pq.add(parent);

medium

A. Node class must implement Comparable for PriorityQueue

B. Cannot add null character to Node

C. PriorityQueue should be initialized with capacity

D. Must poll three nodes before creating parent

Solution

1. Step 1: Check PriorityQueue usage

   PriorityQueue requires elements to be comparable or a comparator provided to order nodes by frequency.

2. Step 2: Verify Node class implementation

   If Node does not implement Comparable or no comparator is given, pq.poll() will throw runtime error.

3. Final Answer:

   Node class must implement Comparable for PriorityQueue -> Option A

4. Quick Check:

   PriorityQueue needs Comparable nodes [OK]

Hint: Ensure Node implements Comparable for PriorityQueue [OK]

Common Mistakes:

• Ignoring Comparable interface requirement
• Thinking null character is invalid here
• Assuming PriorityQueue needs capacity argument

5. Given a string "abbcccdddd", how many bits will Huffman Encoding save compared to fixed-length 3-bit encoding per character?

hard

A. 7 bits saved

B. 10 bits saved

C. 11 bits saved

D. 15 bits saved

Solution

1. Step 1: Calculate fixed-length bits

   String length is 10, fixed-length 3 bits per char, total bits = 10*3 = 30 bits.

2. Step 2: Calculate Huffman bits

   Frequencies: a=1, b=2, c=3, d=4. Huffman codes: a:100 (3 bits), b:101 (3), c:11 (2), d:0 (1). Total bits = (1*3) + (2*3) + (3*2) + (4*1) = 3 + 6 + 6 + 4 = 19 bits.

3. Step 3: Calculate bits saved

   Bits saved = 30 - 19 = 11 bits.

4. Final Answer:

   11 bits saved -> Option C

5. Quick Check:

   Fixed 30 bits - Huffman 19 bits = 11 bits saved [OK]

Hint: Calculate fixed bits minus Huffman bits for savings [OK]

Common Mistakes:

• Not counting frequencies correctly
• Using wrong bit length for fixed encoding
• Miscomputing total Huffman bits