Introduction
Huffman coding is a greedy algorithm used to build an optimal prefix-free binary code for a set of symbols based on their frequencies of occurrence. Frequent symbols get shorter codes and rare symbols get longer codes, which minimizes the total encoded length compared to any fixed-length encoding scheme. It is the foundation for lossless compression formats such as DEFLATE (used in ZIP and gzip) and JPEG's entropy coding stage.
Cricket analogy: Huffman coding is like giving your fastest scorers, the frequent symbols, the shortest boundary calls to make and your rare tail-enders the longest build-up overs, minimizing total commentary time across an innings.
Algorithm/Syntax
import heapq
from collections import Counter
class Node:
def __init__(self, char, freq, left=None, right=None):
self.char = char
self.freq = freq
self.left = left
self.right = right
# heapq needs a way to compare nodes with equal-ish priority
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(text):
freq = Counter(text)
heap = [Node(ch, f) for ch, f in freq.items()]
heapq.heapify(heap)
# Repeatedly merge the two lowest-frequency nodes until one remains
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = Node(None, left.freq + right.freq, left, right)
heapq.heappush(heap, merged)
return heap[0] # root of the Huffman tree
Explanation
The algorithm uses a min-priority queue keyed on frequency. At each step it greedily removes the two least-frequent nodes and merges them into a new internal node whose frequency is their sum, then pushes that node back into the queue. This greedy choice -- always combining the two rarest symbols/subtrees first -- guarantees the least-frequent symbols end up deepest in the tree (longest codes) and the most-frequent symbols end up shallowest (shortest codes), which minimizes the weighted path length (the expected code length). Once only one node remains, it is the root, and each leaf's code is the sequence of left/right edges (0/1) from root to leaf, which is automatically prefix-free because every symbol is a leaf.
Cricket analogy: The selectors repeatedly pick the two weakest available batters, pair them into a partnership, and treat that partnership's combined average as a single unit for the next round, until one final combined team remains, mirroring Huffman's repeated merging of the two rarest nodes.
Prefix-free means no code is a prefix of any other code. This property is what allows a decoder to unambiguously split a bitstream back into symbols without needing delimiters, and it falls out naturally because every character lives at a leaf of the binary tree.
Example
def generate_codes(node, prefix="", code_map=None):
if code_map is None:
code_map = {}
if node is None:
return code_map
if node.char is not None: # leaf node
code_map[node.char] = prefix or "0" # handle single-symbol edge case
return code_map
generate_codes(node.left, prefix + "0", code_map)
generate_codes(node.right, prefix + "1", code_map)
return code_map
text = "aaaaabbbccd" # frequencies: a=5, b=3, c=2, d=1
root = build_huffman_tree(text)
codes = generate_codes(root)
print(codes)
# Trace: heap starts as [d:1, c:2, b:3, a:5]
# merge d(1)+c(2) -> dc:3 heap: [b:3, dc:3, a:5]
# merge b(3)+dc(3) -> bdc:6 heap: [a:5, bdc:6]
# merge a(5)+bdc(6) -> root:11
# Resulting codes (one valid assignment): a='0', b='11', c='101', d='100'
# Encoded length = 5*1 + 3*2 + 2*3 + 1*3 = 5+6+6+3 = 20 bits
# vs fixed-length 3 bits/symbol * 11 symbols = 33 bits -- Huffman saves 13 bits
encoded = "".join(codes[ch] for ch in text)
print(encoded, len(encoded))
Complexity
Building the initial heap of n distinct symbols takes O(n). Each of the n-1 merge steps performs two heap pops and one push, each O(log n), giving O(n log n) overall for tree construction. Generating codes via a tree traversal is O(n). Total time complexity is O(n log n), where n is the number of distinct symbols (not the length of the input text), with O(n) space for the tree and frequency table.
Cricket analogy: Seeding an initial squad list of n players is quick, but each of the n-1 pairing rounds costs O(log n) to find the next weakest pair, giving O(n log n) total, the same shape as Huffman tree construction.
Key Takeaways
- Huffman coding assigns shorter bit codes to more frequent symbols and longer codes to rarer symbols.
- The greedy step is always merging the two lowest-frequency nodes in a min-priority queue.
- The resulting binary tree structure guarantees prefix-free codes, enabling unambiguous decoding.
- Time complexity is O(n log n) for n distinct symbols, driven by repeated heap operations.
- It underlies real-world compression formats like ZIP/DEFLATE and JPEG.
Practice what you learned
1. What data structure is used to efficiently select the two lowest-frequency nodes at each step of Huffman coding?
2. Why are Huffman codes guaranteed to be prefix-free?
3. What is the time complexity of building a Huffman tree for n distinct symbols?
4. In Huffman coding, what greedy choice is made at each iteration?
Was this page helpful?
You May Also Like
The Greedy Algorithm Paradigm
Learn how greedy algorithms build solutions one locally optimal choice at a time, and when that strategy actually yields a global optimum.
Trie-Based String Algorithms
Learn how a trie (prefix tree) organizes strings for fast insertion, search, and prefix queries.
Algorithm Complexity Cheat Sheet
A reference summary of time and space complexities for the major algorithms covered in this course.
Activity Selection Problem
Select the maximum number of non-overlapping activities from a schedule using a greedy earliest-finish-time strategy.