Huffman Encoding

Problem Statement

Given characters and their frequencies, construct a Huffman code (variable-length prefix code) to minimize total encoding length. This hard-level greedy problem is about compression—encode efficiently!

Example

Input: chars = ['a', 'b', 'c'], freq = [5, 9, 12]

Output: {'a': '00', 'b': '1', 'c': '01'} (length = 5*2 + 9*1 + 12*2 = 43)

Input: chars = ['a', 'b'], freq = [1, 1]

Output: {'a': '0', 'b': '1'}

Code

import java.util.*;
public class Solution {
    class Node {
        char ch; int freq; Node left, right;
        Node(char ch, int freq) { this.ch = ch; this.freq = freq; }
    }
    public Map huffmanEncoding(char[] chars, int[] freq) {
        PriorityQueue pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);
        for (int i = 0; i < chars.length; i++) pq.add(new Node(chars[i], freq[i]));
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node('\0', left.freq + right.freq);
            parent.left = left; parent.right = right;
            pq.add(parent);
        }
        Map codes = new HashMap<>();
        generateCodes(pq.peek(), "", codes);
        return codes;
    }
    private void generateCodes(Node root, String code, Map codes) {
        if (root == null) return;
        if (root.left == null && root.right == null) codes.put(root.ch, code);
        generateCodes(root.left, code + "0", codes);
        generateCodes(root.right, code + "1", codes);
    }
}
            

from heapq import heappush, heappop
class Node:
    def __init__(self, ch, freq): self.ch, self.freq, self.left, self.right = ch, freq, None, None
    def __lt__(self, other): return self.freq < other.freq
def huffman_encoding(chars, freq):
    pq = []
    for ch, f in zip(chars, freq): heappush(pq, Node(ch, f))
    while len(pq) > 1:
        left = heappop(pq)
        right = heappop(pq)
        parent = Node(None, left.freq + right.freq)
        parent.left, parent.right = left, right
        heappush(pq, parent)
    codes = {}
    def generate_codes(node, code=""): 
        if not node: return
        if not node.left and not node.right: codes[node.ch] = code
        generate_codes(node.left, code + "0")
        generate_codes(node.right, code + "1")
    generate_codes(pq[0])
    return codes
            

class Node {
    constructor(ch, freq) { this.ch = ch; this.freq = freq; this.left = null; this.right = null; }
}
function huffmanEncoding(chars, freq) {
    let pq = [];
    for (let i = 0; i < chars.length; i++) pq.push(new Node(chars[i], freq[i]));
    pq.sort((a, b) => a.freq - b.freq);
    while (pq.length > 1) {
        let left = pq.shift();
        let right = pq.shift();
        let parent = new Node(null, left.freq + right.freq);
        parent.left = left; parent.right = right;
        pq.push(parent); pq.sort((a, b) => a.freq - b.freq);
    }
    let codes = {};
    function generateCodes(node, code = "") {
        if (!node) return;
        if (!node.left && !node.right) codes[node.ch] = code;
        generateCodes(node.left, code + "0");
        generateCodes(node.right, code + "1");
    }
    generateCodes(pq[0]);
    return codes;
}
            

Explanation

• Greedy Choice: Combine two lowest-frequency nodes iteratively.
• Flow: Build a tree, assign codes via traversal.
• Example: ['a',5],['b',9],['c',12] → combine 5+9, then with 12.

Note