Huffman Coding (Optimal Prefix-Free Compression)
Huffman Coding constructs an optimal variable-length prefix-free binary encoding for symbol frequencies in O(n log n) time by greedily merging the two lowest-frequency nodes with a min-heap.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Huffman Coding (Optimal Prefix-Free Compression)
Huffman Coding is the foundation of lossless data compression (DEFLATE, ZIP, PNG, JPEG, MP3). Given symbols with frequencies $f_1, \dots, f_n$, it assigns shorter bit codes to frequent symbols and longer codes to rare symbols such that no code is a prefix of another (prefix-free). Repeatedly merging the two lowest-frequency trees in a min-Heap produces a provably optimal minimum-bit encoding in $O(n \log n)$ time!
At a Glance
| Property | Value |
| :--- | :---: |
| Time Complexity | $O(n \log n)$ (min-heap) / $O(n)$ if frequencies are already sorted (2 queues) |
| Auxiliary Space | $O(n)$ |
| Key Property | Optimal prefix-free code minimizing $\sum f_i \cdot \text{depth}(i)$ |
---
Practice Problems
Easy
1. Minimum Total Encoded Bits (Connect Ropes / Huffman Cost)
Given symbol frequencies freq[], compute the exact minimum total bits required by an optimal Huffman code (equivalently, minimum cost to merge ropes!).
Approach: Push all frequencies into a min-heap; repeatedly pop the two smallest a, b, add a + b to totalBits, and push a + b back until 1 node remains! Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
long long huffmanTotalBits(const std::vector<int>& freq) {
if (freq.size() <= 1) return freq.empty() ? 0 : freq[0];
std::priority_queue<long long, std::vector<long long>, std::greater<long long>> pq(freq.begin(), freq.end());
long long total = 0;
while (pq.size() > 1) {
long long a = pq.top(); pq.pop();
long long b = pq.top(); pq.pop();
total += a + b;
pq.push(a + b);
}
return total;
}
int main() {
std::cout << huffmanTotalBits({5, 9, 12, 13, 16, 45}) << "\n"; // 224
return 0;
}
</details>
Intermediate
2. Build the Huffman Tree & Generate Bit Codes
Construct the full Huffman binary tree for (char, freq) pairs and output each character's prefix-free binary code.
Approach: Use a min-heap of Node*, merge the two smallest into a parent node, then DFS assigning '0' for left edges and '1' for right edges. Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <utility>
#include <vector>
struct HNode {
char ch;
int freq;
HNode *l = nullptr, *r = nullptr;
HNode(char c, int f, HNode* l = nullptr, HNode* r = nullptr) : ch(c), freq(f), l(l), r(r) {}
};
void collectCodes(HNode* u, const std::string& cur, std::map<char, std::string>& codes) {
if (!u) return;
if (!u->l && !u->r) { codes[u->ch] = cur.empty() ? "0" : cur; return; }
collectCodes(u->l, cur + "0", codes);
collectCodes(u->r, cur + "1", codes);
}
void freeH(HNode* u) { if (!u) return; freeH(u->l); freeH(u->r); delete u; }
int main() {
std::vector<std::pair<char, int>> syms = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};
auto cmp = [](HNode* a, HNode* b) { return a->freq > b->freq; };
std::priority_queue<HNode*, std::vector<HNode*>, decltype(cmp)> pq(cmp);
for (const auto& [c, f] : syms) pq.push(new HNode(c, f));
while (pq.size() > 1) {
HNode* a = pq.top(); pq.pop();
HNode* b = pq.top(); pq.pop();
pq.push(new HNode('\0', a->freq + b->freq, a, b));
}
std::map<char, std::string> codes;
collectCodes(pq.top(), "", codes);
for (const auto& [c, code] : codes) std::cout << c << ":" << code << " ";
std::cout << "\n";
freeH(pq.top());
return 0;
}
</details>
---
Related Structures & Algorithms
- Binary Heap — priority queue driving Huffman merges.
- Binary Tree — tree representation of prefix-free codes.