Huffman Coding
Huffman coding is an optimal prefix-free binary code used for data compression. It builds a binary tree where the most frequent characters have the shortest codes. Greedy: repeatedly combine the two nodes with smallest frequency.
Algorithm:
1. Create a min-heap of leaf nodes (each with character and frequency).
2. While more than one node, pop two smallest, create a new node with sum frequency, push back.
3. The final node is the root of the Huffman tree.
Java implementation skeleton:
static class Node { int freq; char ch; Node left, right; }
public static Node buildHuffmanTree(int[] freqs, char[] chars) {
PriorityQueue pq = new PriorityQueue<>((a,b) -> a.freq - b.freq);
for (int i = 0; i < chars.length; i++) {
Node leaf = new Node(); leaf.ch = chars[i]; leaf.freq = freqs[i];
pq.add(leaf);
}
while (pq.size() > 1) {
Node left = pq.poll(); Node right = pq.poll();
Node parent = new Node();
parent.freq = left.freq + right.freq;
parent.left = left; parent.right = right;
pq.add(parent);
}
return pq.poll();
}
Two Minute Drill
- Huffman coding creates optimal prefix-free codes.
- Greedy: combine two smallest frequencies.
- Build tree using min-heap; O(n log n).
- Used in compression algorithms (ZIP, JPEG).
Need more clarification?
Drop us an email at career@quipoinfotech.com