AntInLoop

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.