DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Build Huffman codes from scratch — understand frequency-based prefix codes, priority queue construction, tree building, encoding/decoding, and compression analysis.
What is Huffman Coding?
Huffman coding is a greedy algorithm that produces optimal prefix-free variable-length codes for data compression. Characters that appear frequently get shorter bit sequences, while rare characters get longer ones. The result: the encoded message uses fewer total bits than a fixed-length encoding.
The Core Idea
In ASCII, every character takes 8 bits regardless of frequency. But if 'e' appears 1000 times and 'z' appears once, giving 'e' a 2-bit code and 'z' a 10-bit code saves enormous space. The challenge: how do you assign codes so that no code is a prefix of another (ensuring unambiguous decoding)?
Huffman's insight: build a binary tree bottom-up, repeatedly merging the two least-frequent nodes. The path from root to leaf gives each character's code (left = 0, right = 1).
Algorithm Steps
- Count the frequency of each character in the input.
- Create a leaf node for each character and insert into a min-priority queue (keyed by frequency).
- While the queue has more than one node:
a. Extract the two nodes with lowest frequency (call them left and right). b. Create a new internal node with frequency = left.freq + right.freq. c. Set left and right as children of this new node. d. Insert the new node back into the priority queue.
- The last remaining node is the root of the Huffman tree.
- Traverse the tree to assign codes: going left adds '0', going right adds '1'.
Dry Run Example
| Input | "ABRACADABRA" |
| Frequencies | A=5, B=2, R=2, C=1, D=1 |
| Step 1 | Priority queue: [C:1, D:1, B:2, R:2, A:5] |
| Step 2: Merge C(1) + D(1) | CD(2) |
| Queue | [B:2, R:2, CD:2, A:5] |
| Step 3: Merge B(2) + R(2) | BR(4) |
| Queue | [CD:2, A:5, BR:4] |
| Step 4: Merge CD(2) + BR(4) | CDBR(6) |
| Wait — min is CD | 2 and A:5? No, re-sort: [CD:2, BR:4, A:5] |
| Merge CD(2) + BR(4) | CDBR(6) |
| Queue | [A:5, CDBR:6] |
| Step 5: Merge A(5) + CDBR(6) | Root(11) |
| Codes | A=0, C=100, D=101, B=110, R=111 |
| Compression ratio | 23/33 = 69.7% (saved 30.3%) |
Python Implementation
Example
import heapq
from collections import Counter
class HuffmanNode:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(text):
freq = Counter(text)
# Create priority queue of leaf nodes
heap = [HuffmanNode(char, f) for char, f in freq.items()]
heapq.heapify(heap)
# Build tree by merging two smallest nodes
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = HuffmanNode(None, left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(heap, merged)
return heap[0] # root
def generate_codes(root):
codes = {}
def traverse(node, code):
if node is None:
return
if node.char is not None: # leaf node
codes[node.char] = code if code else "0" # single-char edge case
return
traverse(node.left, code + "0")
traverse(node.right, code + "1")
traverse(root, "")
return codes
def huffman_encode(text):
root = build_huffman_tree(text)
codes = generate_codes(root)
encoded = "".join(codes[char] for char in text)
return encoded, codes, root
def huffman_decode(encoded, root):
decoded = []
node = root
for bit in encoded:
node = node.left if bit == "0" else node.right
if node.char is not None: # reached a leaf
decoded.append(node.char)
node = root # restart from root
return "".join(decoded)
# Test
text = "ABRACADABRA"
encoded, codes, root = huffman_encode(text)
print(f"Original: {text}")
print(f"Codes: {codes}")
print(f"Encoded: {encoded} ({len(encoded)} bits)")
print(f"Fixed-length would need: {len(text) * 3} bits")
print(f"Decoded: {huffman_decode(encoded, root)}")
C++ Implementation
Example
#include <queue>
#include <unordered_map>
#include <string>
#include <iostream>
using namespace std;
struct HuffNode {
char ch;
int freq;
HuffNode *left, *right;
HuffNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
struct Compare {
bool operator()(HuffNode* a, HuffNode* b) { return a->freq > b->freq; }
};
void buildCodes(HuffNode* root, string code, unordered_map<char,string>& codes) {
if (!root) return;
if (root->ch != '\0') {
codes[root->ch] = code.empty() ? "0" : code;
return;
}
buildCodes(root->left, code + "0", codes);
buildCodes(root->right, code + "1", codes);
}
unordered_map<char,string> huffmanCoding(const string& text) {
unordered_map<char,int> freq;
for (char c : text) freq[c]++;
priority_queue<HuffNode*, vector<HuffNode*>, Compare> pq;
for (auto& [ch, f] : freq)
pq.push(new HuffNode(ch, f));
while (pq.size() > 1) {
HuffNode* left = pq.top(); pq.pop();
HuffNode* right = pq.top(); pq.pop();
HuffNode* merged = new HuffNode('\0', left->freq + right->freq);
merged->left = left;
merged->right = right;
pq.push(merged);
}
unordered_map<char,string> codes;
buildCodes(pq.top(), "", codes);
return codes;
}
Why Huffman Codes Are Optimal
Huffman produces the optimal prefix code (minimum expected bit length) for a given frequency distribution. The greedy choice: always merging the two least frequent nodes ensures that rare characters end up deepest in the tree (longest codes) and frequent characters stay near the root (shortest codes).
Proof sketch: If we swapped a deep frequent character with a shallow rare one, total bits would increase (more occurrences × longer code > fewer occurrences × longer code).
Complexity Analysis
| Operation | Time | Notes |
|---|---|---|
| Frequency counting | O(n) | n = input length |
| Building heap | O(k log k) | k = unique characters |
| Tree construction | O(k log k) | k-1 merges, each O(log k) |
| Code generation | O(k) | Tree traversal |
| Encoding | O(n) | One lookup per character |
| Decoding | O(m) | m = encoded bit length |
| Total | O(n + k log k) |
Compression Ratio
The theoretical compression ratio depends on entropy H:
Example
H = -Σ p(cᵢ) × log₂(p(cᵢ))
Huffman average code length L satisfies:
H ≤ L < H + 1
For our example: H ≈ 2.04 bits/char, Huffman gives L = 23/11 ≈ 2.09 bits/char
Huffman is within 1 bit of the entropy lower bound per character.
Real-World Applications
- ZIP/GZIP compression: Uses Huffman as part of the DEFLATE algorithm
- JPEG images: Huffman coding for quantized DCT coefficients
- MP3 audio: Huffman tables for encoded frequency data
- Fax machines (Group 3): Modified Huffman for run-length encoded data
- HTTP/2: HPACK header compression uses Huffman-coded strings
Key Takeaways
Huffman coding is a beautiful example of greedy optimality. The min-heap merge strategy guarantees optimal prefix codes. The algorithm runs in O(n + k log k) time and achieves compression within 1 bit/symbol of the theoretical entropy limit. It remains the foundation of modern lossless compression despite being invented in 1952.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Huffman Coding — Data Structures & Algorithms.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, greedy, huffman, coding
Related Data Structures & Algorithms Topics
Continue learning this concept
Greedy AlgorithmsActivity Selection ProblemSolve the Activity Selection problem with a greedy approach — sort by finish time, select non-overlapping activities, and prove optimality via exchange argument.Greedy AlgorithmsFractional KnapsackSolve the Fractional Knapsack problem using a greedy approach — sort by value-to-weight ratio, fill optimally, and understand why fractions make greedy work.Greedy AlgorithmsGreedy Interview ProblemsMaster four classic greedy interview problems — Minimum Platforms, Gas Station Circuit, Jump Game, and Candy Distribution with detailed approaches and code.Greedy AlgorithmsGreedy Algorithm FundamentalsUnderstand greedy algorithms — the greedy choice property, optimal substructure, when greedy works vs fails, and techniques to prove correctness.Greedy AlgorithmsJob Sequencing with DeadlinesSolve the Job Sequencing problem using a greedy approach — maximize profit by sorting by profit and assigning each job to the latest available time slot before its deadline.Interview PreparationEssential Coding Patterns for InterviewsMaster the 7 most important coding patterns: sliding window, two pointers, fast & slow pointers, merge intervals, cyclic sort, top-K elements, and modified binary search.